×

zbMATH — the first resource for mathematics

Kirkpatrick, David G.

Compute Distance To:
Author ID: kirkpatrick.david-g Recent zbMATH articles by "Kirkpatrick, David G."
Published as: Kirkpatrick, David; Kirkpatrick, David G.; Kirkpatrick, D. G.; Kirkpatrick, D.
Documents Indexed: 115 Publications since 1972, including 2 Books
all top 5

Co-Authors

11 single-authored
12 Hell, Pavol
11 Evans, William S.
7 Snoeyink, Jack Scott
6 Adler, Andrew
6 Higham, Lisa
5 Asano, Tetsuo
5 Corneil, Derek Gordon
5 Dobkin, David P.
5 Klawe, Maria Margaret
5 Speckmann, Bettina
4 Bose, Prosenjit K.
4 Durocher, Stephane
4 Seidel, Raimund
3 Bereg, Sergey N.
3 Bespamyatnikh, Sergei N.
3 Dadoun, N.
3 Edelsbrunner, Herbert
3 Przytycka, Teresa M.
3 Saitoh, Toshiki
3 Yap, Chee-Keng
3 Zilles, Sandra
2 Backer, Jonathan
2 Bhattacharya, Binay Kumar
2 Chan, David Yu Cheng
2 Devroye, Luc P. J. A.
2 Horiyama, Takashi
2 Keil, J. Mark
2 Löffler, Maarten
2 Otachi, Yota
2 Pippenger, Nicholas J.
2 Segal, Michael
2 Staals, Frank
2 Uehara, Ryuhei
2 Uno, Yushi
2 Wismath, Stephen K.
2 Yamanaka, Katsuhisa
1 Alvarez, Victor
1 Archambault, Daniel
1 Bespamyatnikh, B.
1 Borodin, Allan B.
1 Breu, Heinz
1 Bshouty, Nader H.
1 Busto, Daniel
1 Condon, Anne E.
1 Eriksson-Bique, Sylvester
1 Fischer, Michael J.
1 Fraisse, Pierre
1 Gao, Ziyuan
1 Gelbart, Rachel
1 Gethner, Ellen
1 Gowda, Ihor G.
1 Guibas, Leonidas John
1 Hajiaghayi, Monir
1 Heinrich, Katherine
1 Hershberger, John E.
1 Kaminsky, Michael
1 Kedem, Zvi Meir
1 Keil, Mark J.
1 Kettner, Lutz
1 Kratochvíl, Jan
1 Kříž, Igor
1 Laaser, William T.
1 Lee, Der-Tsai
1 Li, Brenda
1 Li, Zaiqing
1 Liu, Guizhen
1 Lynch, Nancy Ann
1 Mantler, Andrea
1 Maňuch, Ján
1 Maurer, Hermann A.
1 McAllister, Michael
1 Mishra, Bhubaneswar
1 Naamad, Amnon
1 Nakagawa, Kotaro
1 Narayanan, Lata
1 Polishchuk, Valentin
1 Rangan, Chandrasekharan Pandu
1 Reddy, K. Madhukar
1 Reisch, Stefan
1 Ries, Christoph
1 Saxe, James B.
1 Simon, Hans-Ulrich
1 Suri, Subhash
1 Takeuchi, Fumihiko
1 Tarjan, Robert Endre
1 Tompa, Martin
1 Townsend, Gregg M.
1 Tseng, Kuan-Chieh Robert
1 Tseng, Wei-Lung Dustin
1 Watanabe, Osamu
1 Yang, Boting

Publications by Year

Citations contained in zbMATH Open

95 Publications have been cited 1,155 times in 956 Documents Cited by Year
Optimal search in planar subdivisions. Zbl 0501.68034
Kirkpatrick, David
141
1983
On the shape of a set of points in the plane. Zbl 0512.52001
Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund
74
1983
On the complexity of general graph factor problems. Zbl 0525.68023
Kirkpatrick, D. G.; Hell, P.
67
1983
The ultimate planar convex hull algorithm ? Zbl 0589.68035
Kirkpatrick, David G.; Seidel, Raimund
64
1986
On the completeness of a generalized matching problem. Zbl 1282.68182
Kirkpatrick, David G.; Hell, Pavol
57
1978
Unit disk graph recognition is NP-hard. Zbl 0894.68099
Breu, Heinz; Kirkpatrick, David G.
54
1998
A simple parallel tree contraction algorithm. Zbl 0681.68085
Abrahamson, K.; Dadoun, N.; Kirkpatrick, D. G.; Przytycka, T.
47
1989
Fast detection of polyhedral intersection. Zbl 0553.68033
Dobkin, David P.; Kirkpatrick, David G.
35
1983
A linear algorithm for determining the separation of convex polyhedra. Zbl 0577.52004
Dobkin, David P.; Kirkpatrick, David G.
35
1985
Determining the separation of preprocessed polyhedra – A unified approach. Zbl 0765.68205
Dobkin, David P.; Kirkpatrick, David G.
30
1990
Packings by cliques and by finite families of graphs. Zbl 0582.05046
Hell, P.; Kirkpatrick, D. G.
26
1984
Generalizing ham sandwich cuts to equitable subdivisions. Zbl 0966.68156
Bespamyatnikh, S.; Kirkpatrick, D.; Snoeyink, J.
24
2000
Packings by complete bipartite graphs. Zbl 0597.05050
Hell, P.; Kirkpatrick, D. G.
21
1986
A compact piecewise-linear Voronoi diagram for convex sites in the plane. Zbl 0840.68119
McAllister, M.; Kirkpatrick, D.; Snoeyink, J.
20
1996
A simple existence criterion for \((g<f)\)-factors. Zbl 0723.05101
Heinrich, Katherine; Hell, Pavol; Kirkpatrick, David G.; Liu, Guizhen
18
1990
Upper bounds for sorting integers on random access machines. Zbl 0533.68046
Kirkpatrick, David; Reisch, Stefan
17
1984
Algorithms for degree constrained graph factors of minimum deficiency. Zbl 0764.68118
Hell, P.; Kirkpatrick, D. G.
16
1993
Computing the intersection-depth to polyhedra. Zbl 0797.68162
Dobkin, David; Hershberger, John; Kirkpatrick, David; Suri, Subhash
15
1993
A note on Delaunay and optimal triangulations. Zbl 0458.05011
Kirkpatrick, David G.
15
1980
A time-space tradeoff for sorting on non-oblivious machines. Zbl 0462.68011
Borodin, Allan; Fischer, Michael J.; Kirkpatrick, David G.; Lynch, Nancy A.; Tompa, Martin
15
1981
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Zbl 1022.05078
Bose, Prosenjit; Kirkpatrick, David; Li, Zaiqing
14
2003
Tentative prune-and-search for computing fixed-points with applications to geometric computation. Zbl 0815.68119
Kirkpatrick, David; Snoeyink, Jack
14
1995
Kinetic collision detection for simple polygons. Zbl 1152.68671
Kirkpatrick, David; Snoeyink, Jack; Speckmann, Bettina
14
2002
On restricted two-factors. Zbl 0672.05065
Hell, Pavol; Kirkpatrick, David; Kratochvíl, Jan; Kříž, Igor
13
1988
On generalized matching problems. Zbl 0454.68077
Hell, P.; Kirkpatrick, D. G.
13
1981
A unified lower bound for selection and set partitioning problems. Zbl 0454.68076
Kirkpatrick, David G.
12
1981
Polygonal intersection searching. Zbl 0486.68051
Edelsbrunner, H.; Maurer, H. A.; Kirkpatrick, D. G.
12
1982
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. Zbl 1414.68130
Kirkpatrick, David; Speckmann, Bettina
11
2002
Tight degree bounds for pseudo-triangulations of points. Zbl 1023.65013
Kettner, Lutz; Kirkpatrick, David; Mantler, Andrea; Snoeyink, Jack; Speckmann, Bettina; Takeuchi, Fumihiko
10
2003
Improved approximation for guarding simple galleries from the perimeter. Zbl 1226.68122
King, James; Kirkpatrick, David
10
2011
On the spanning ratio of Gabriel graphs and \(\beta\)-skeletons. Zbl 1115.68107
Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David
10
2006
Addition requirements for matrix and transposed matrix products. Zbl 0653.65032
Kaminski, Michael; Kirkpatrick, David G.; Bshouty, Nader H.
8
1988
Right-triangulated irregular networks. Zbl 0984.65014
Evans, W.; Kirkpatrick, D.; Townsend, G.
8
2001
Efficient algorithms for centers and medians in interval and circular-arc graphs. Zbl 1001.90055
Bespamyatnikh, Sergei; Bhattacharya, Binay; Keil, Mark; Kirkpatrick, David; Segal, Michael
8
2002
A theoretical analysis of various heuristics for the graph isomorphism problem. Zbl 0451.05043
Corneil, D. G.; Kirkpatrick, D. G.
8
1980
Hyperbolic dovetailing. Zbl 1256.68164
Kirkpatrick, David
8
2009
The Steiner centre of a set of points: stability, eccentricity, and applications to mobile facility location. Zbl 1104.65020
Durocher, Stephane; Kirkpatrick, David
8
2006
Families of recursively defined perfect graphs. Zbl 0576.05023
Corneil, D. G.; Kirkpatrick, D. G.
8
1983
Parallel construction of subdivision hierarchies. Zbl 0678.68056
Dadoun, N.; Kirkpatrick, D. G.
7
1989
Time-space tradeoffs for all-nearest-larger-neighbors problems. Zbl 1390.68328
Asano, Tetsuo; Kirkpatrick, David
7
2013
Swapping colored tokens on graphs. Zbl 1451.68135
Yamanaka, Katsuhisa; Horiyama, Takashi; Kirkpatrick, David; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei; Uno, Yushi
6
2015
The projection median of a set of points. Zbl 1170.65013
Durocher, Stephane; Kirkpatrick, David
6
2009
Quantitative Steinitz’s theorems with applications to multifingered grasping. Zbl 0747.52004
Kirkpatrick, David; Mishra, Bhubaneswar; Yap, Chee-Keng
5
1992
Parallel recognition of complement reducible graphs and cotree construction. Zbl 0707.68039
Kirkpatrick, D. G.; Przytycka, T.
5
1990
Scheduling, matching, and coloring. Zbl 0474.05054
Hell, P.; Kirkpatrick, D. G.
5
1981
Equitable subdivisions within polygonal regions. Zbl 1098.65023
Bereg, Sergey; Bose, Prosenjit; Kirkpatrick, David
5
2006
Bounded-velocity approximation of mobile Euclidean 2-centres. Zbl 1155.65018
Durocher, Stephane; Kirkpatrick, David
5
2008
Dynamic Voronoi diagrams. Zbl 0516.94030
Gowda, Ihor G.; Kirkpatrick, David G.; Lee, Der Tsai; Naamad, Amnon
5
1983
Alphabetic minimax trees. Zbl 0565.94025
Kirkpatrick, David G.; Klawe, Maria M.
5
1985
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. Zbl 1318.68059
Evans, William; Kirkpatrick, David
5
2004
The bit complexity of randomized leader election on a ring. Zbl 0674.68029
Abrahamson, Karl; Adler, Andrew; Gelbart, Rachel; Higham, Lisa; Kirkpatrick, David
4
1989
Parallel algorithms for fractional and maximal independent sets in planar graphs. Zbl 0699.68086
Dadoun, N.; Kirkpatrick, D. G.
4
1990
Pseudo approximation algorithms with applications to optimal motion planning. Zbl 1060.68126
Asano, Tetsuo; Kirkpatrick, David; Yap, Chee
4
2004
Fast detection of polyhedral intersections. Zbl 0494.68056
Dobkin, David P.; Kirkpatrick, David G.
4
1982
Finding nearest larger neighbors. A case study in algorithm design and analysis. Zbl 1258.68178
Asano, Tetsuo; Bereg, Sergey; Kirkpatrick, David
4
2009
Linear-time certifying algorithms for near-graphical sequences. Zbl 1185.05135
Hell, Pavol; Kirkpatrick, David
4
2009
Determining graph properties from matrix representations. Zbl 0358.68060
Kirkpatrick, David
4
1974
Kinetic collision detection for simple polygons. Zbl 1375.68151
Kirkpatrick, David; Snoeyink, Jack; Speckmann, Bettina
4
2000
Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience. Zbl 1417.68283
Chan, David Yu Cheng; Kirkpatrick, David
4
2014
\(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability. Zbl 1426.68196
Asano, Tetsuo; Kirkpatrick, David; Nakagawa, Kotaro; Watanabe, Osamu
4
2014
On pseudosimilarity in trees. Zbl 0536.05056
Kirkpatrick, D. G.; Klawe, M. M.; Corneil, D. G.
4
1983
Randomized function evaluation on a ring. Zbl 0703.68057
Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David
3
1989
Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures. Zbl 0753.68092
Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E.
3
1992
Weighted visibility graphs of bars and related flow problems. (Extended abstract). Zbl 0765.68159
Kirkpatrick, David G.; Wismath, Stephen K.
3
1989
Establishing order in planar subdivisions. Zbl 0663.68053
Kirkpatrick, David G.
3
1988
Separation sensitive kinetic separation structures for convex polygons. Zbl 0990.68164
Kirkpatrick, David; Speckmann, Bettina
3
2001
Input-thrifty extrema testing. Zbl 1350.68157
Tseng, Kuan-Chieh Robert; Kirkpatrick, David
3
2011
Restructuring ordered binary trees. Zbl 1067.68101
Evans, William; Kirkpatrick, David
3
2004
Constrained equitable \(3\)-cuttings. Zbl 1179.52003
Bespamyatnikh, Sergei; Kirkpatrick, David
3
2003
Tight lower bounds for probabilistic solitude verification on anonymous rings. Zbl 0806.68038
Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David
2
1994
Rounding in symmetric matrices and undirected graphs. Zbl 0920.05062
Hell, Pavol; Kirkpatrick, David; Li, Brenda
2
1996
Optimal algorithm for probabilistic solitude detection on anonymous rings. Zbl 0873.68080
Higham, Lisa; Kirkpatrick, David; Abrahamson, Karl; Adler, Andrew
2
1997
A note on f-factors in directed and undirected multigraphs. Zbl 0594.05053
Fraisse, Pierre; Hell, Pavol; Kirkpatrick, David G.
2
1986
Parallel construction of binary trees with near optimal weighted path length. Zbl 0836.68053
Kirkpatrick, D. G.; Przytycka, T.
2
1996
Lower bounds on average-case delay for video-on-demand broadcast protocols. Zbl 1302.68029
Tseng, Wei-Lung Dustin; Kirkpatrick, David
2
2007
Forest embeddings in regular graphs of large girth. Zbl 0394.05016
Kirkpatrick, D. G.; Corneil, D. G.
2
1981
An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries. Zbl 1309.68199
Kirkpatrick, David
2
2015
A polynomial-time algorithm for computing the resilience of arrangements of ray sensors. Zbl 1327.68318
Kirkpatrick, David; Yang, Boting; Zilles, Sandra
2
2014
A complete approximation algorithm for shortest bounded-curvature paths. Zbl 1183.68741
Backer, Jonathan; Kirkpatrick, David
2
2008
Finding curvature-constrained paths that avoid polygonal obstacles. Zbl 1221.68291
Backer, Jonathan; Kirkpatrick, David
2
2007
Curvature-bounded traversals of narrow corridors. Zbl 1380.68381
Bereg, Sergey; Kirkpatrick, David
2
2005
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Zbl 1131.68316
Durocher, Stephane; Kirkpatrick, David; Narayanan, Lata
2
2008
The shape of a set of points in the plane. Zbl 0537.68091
Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R.
2
1982
Some graph-colouring theorems with applications to generalized connection networks. Zbl 0572.05027
Kirkpatrick, David G.; Klawe, Maria; Pippenger, Nicholas
2
1985
Computing constrained shortest segments: Butterfly wingspans in logarithmic time. Zbl 1020.52013
Kirkpatrick, David; Snoeyink, Jack
1
1999
Finding extrema with unary predicates. Zbl 0801.68078
Gao, Feng; Guibas, Leonidas J.; Kirkpatrick, David G.; Laaser, William T.; Saxe, James
1
1993
Finding extrema with unary predicates. Zbl 0819.68062
Kirkpatrick, David G.; Gao, Feng
1
1990
On the spanning ratio of Gabriel graphs and \(\beta\)-skeletons. Zbl 1059.68145
Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David
1
2002
Generalized notions of pseudo-similarity in graphs. Zbl 0461.05045
Corneil, D. G.; Kirkpatrick, D. G.; Klawe, M. M.
1
1980
Competitive search in symmetric trees. Zbl 1342.68339
Kirkpatrick, David; Zilles, Sandra
1
2011
On the additions necessary to compute certain functions. Zbl 0356.65011
Kirkpatrick, David
1
1972
Competitive query strategies for minimising the ply of the potential locations of moving points. Zbl 1305.68231
Evans, William; Kirkpatrick, David; Löffler, Maarten; Staals, Frank
1
2013
Swapping colored tokens on graphs. Zbl 1391.68062
Yamanaka, Katsuhisa; Horiyama, Takashi; Keil, J. Mark; Kirkpatrick, David; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei; Uno, Yushi
1
2018
Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\). Zbl 1394.68185
Kirkpatrick, David
1
2013
Approximating barrier resilience for arrangements of non-identical disk sensors. Zbl 1351.68196
Chan, David Yu Cheng; Kirkpatrick, David
1
2013
Swapping colored tokens on graphs. Zbl 1391.68062
Yamanaka, Katsuhisa; Horiyama, Takashi; Keil, J. Mark; Kirkpatrick, David; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei; Uno, Yushi
1
2018
Swapping colored tokens on graphs. Zbl 1451.68135
Yamanaka, Katsuhisa; Horiyama, Takashi; Kirkpatrick, David; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei; Uno, Yushi
6
2015
An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries. Zbl 1309.68199
Kirkpatrick, David
2
2015
Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience. Zbl 1417.68283
Chan, David Yu Cheng; Kirkpatrick, David
4
2014
\(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability. Zbl 1426.68196
Asano, Tetsuo; Kirkpatrick, David; Nakagawa, Kotaro; Watanabe, Osamu
4
2014
A polynomial-time algorithm for computing the resilience of arrangements of ray sensors. Zbl 1327.68318
Kirkpatrick, David; Yang, Boting; Zilles, Sandra
2
2014
Time-space tradeoffs for all-nearest-larger-neighbors problems. Zbl 1390.68328
Asano, Tetsuo; Kirkpatrick, David
7
2013
Competitive query strategies for minimising the ply of the potential locations of moving points. Zbl 1305.68231
Evans, William; Kirkpatrick, David; Löffler, Maarten; Staals, Frank
1
2013
Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\). Zbl 1394.68185
Kirkpatrick, David
1
2013
Approximating barrier resilience for arrangements of non-identical disk sensors. Zbl 1351.68196
Chan, David Yu Cheng; Kirkpatrick, David
1
2013
Improved approximation for guarding simple galleries from the perimeter. Zbl 1226.68122
King, James; Kirkpatrick, David
10
2011
Input-thrifty extrema testing. Zbl 1350.68157
Tseng, Kuan-Chieh Robert; Kirkpatrick, David
3
2011
Competitive search in symmetric trees. Zbl 1342.68339
Kirkpatrick, David; Zilles, Sandra
1
2011
Hyperbolic dovetailing. Zbl 1256.68164
Kirkpatrick, David
8
2009
The projection median of a set of points. Zbl 1170.65013
Durocher, Stephane; Kirkpatrick, David
6
2009
Finding nearest larger neighbors. A case study in algorithm design and analysis. Zbl 1258.68178
Asano, Tetsuo; Bereg, Sergey; Kirkpatrick, David
4
2009
Linear-time certifying algorithms for near-graphical sequences. Zbl 1185.05135
Hell, Pavol; Kirkpatrick, David
4
2009
Bounded-velocity approximation of mobile Euclidean 2-centres. Zbl 1155.65018
Durocher, Stephane; Kirkpatrick, David
5
2008
A complete approximation algorithm for shortest bounded-curvature paths. Zbl 1183.68741
Backer, Jonathan; Kirkpatrick, David
2
2008
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Zbl 1131.68316
Durocher, Stephane; Kirkpatrick, David; Narayanan, Lata
2
2008
Lower bounds on average-case delay for video-on-demand broadcast protocols. Zbl 1302.68029
Tseng, Wei-Lung Dustin; Kirkpatrick, David
2
2007
Finding curvature-constrained paths that avoid polygonal obstacles. Zbl 1221.68291
Backer, Jonathan; Kirkpatrick, David
2
2007
On the spanning ratio of Gabriel graphs and \(\beta\)-skeletons. Zbl 1115.68107
Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David
10
2006
The Steiner centre of a set of points: stability, eccentricity, and applications to mobile facility location. Zbl 1104.65020
Durocher, Stephane; Kirkpatrick, David
8
2006
Equitable subdivisions within polygonal regions. Zbl 1098.65023
Bereg, Sergey; Bose, Prosenjit; Kirkpatrick, David
5
2006
Curvature-bounded traversals of narrow corridors. Zbl 1380.68381
Bereg, Sergey; Kirkpatrick, David
2
2005
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. Zbl 1318.68059
Evans, William; Kirkpatrick, David
5
2004
Pseudo approximation algorithms with applications to optimal motion planning. Zbl 1060.68126
Asano, Tetsuo; Kirkpatrick, David; Yap, Chee
4
2004
Restructuring ordered binary trees. Zbl 1067.68101
Evans, William; Kirkpatrick, David
3
2004
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Zbl 1022.05078
Bose, Prosenjit; Kirkpatrick, David; Li, Zaiqing
14
2003
Tight degree bounds for pseudo-triangulations of points. Zbl 1023.65013
Kettner, Lutz; Kirkpatrick, David; Mantler, Andrea; Snoeyink, Jack; Speckmann, Bettina; Takeuchi, Fumihiko
10
2003
Constrained equitable \(3\)-cuttings. Zbl 1179.52003
Bespamyatnikh, Sergei; Kirkpatrick, David
3
2003
Kinetic collision detection for simple polygons. Zbl 1152.68671
Kirkpatrick, David; Snoeyink, Jack; Speckmann, Bettina
14
2002
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. Zbl 1414.68130
Kirkpatrick, David; Speckmann, Bettina
11
2002
Efficient algorithms for centers and medians in interval and circular-arc graphs. Zbl 1001.90055
Bespamyatnikh, Sergei; Bhattacharya, Binay; Keil, Mark; Kirkpatrick, David; Segal, Michael
8
2002
On the spanning ratio of Gabriel graphs and \(\beta\)-skeletons. Zbl 1059.68145
Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David
1
2002
Right-triangulated irregular networks. Zbl 0984.65014
Evans, W.; Kirkpatrick, D.; Townsend, G.
8
2001
Separation sensitive kinetic separation structures for convex polygons. Zbl 0990.68164
Kirkpatrick, David; Speckmann, Bettina
3
2001
Generalizing ham sandwich cuts to equitable subdivisions. Zbl 0966.68156
Bespamyatnikh, S.; Kirkpatrick, D.; Snoeyink, J.
24
2000
Kinetic collision detection for simple polygons. Zbl 1375.68151
Kirkpatrick, David; Snoeyink, Jack; Speckmann, Bettina
4
2000
Computing constrained shortest segments: Butterfly wingspans in logarithmic time. Zbl 1020.52013
Kirkpatrick, David; Snoeyink, Jack
1
1999
Unit disk graph recognition is NP-hard. Zbl 0894.68099
Breu, Heinz; Kirkpatrick, David G.
54
1998
Optimal algorithm for probabilistic solitude detection on anonymous rings. Zbl 0873.68080
Higham, Lisa; Kirkpatrick, David; Abrahamson, Karl; Adler, Andrew
2
1997
A compact piecewise-linear Voronoi diagram for convex sites in the plane. Zbl 0840.68119
McAllister, M.; Kirkpatrick, D.; Snoeyink, J.
20
1996
Rounding in symmetric matrices and undirected graphs. Zbl 0920.05062
Hell, Pavol; Kirkpatrick, David; Li, Brenda
2
1996
Parallel construction of binary trees with near optimal weighted path length. Zbl 0836.68053
Kirkpatrick, D. G.; Przytycka, T.
2
1996
Tentative prune-and-search for computing fixed-points with applications to geometric computation. Zbl 0815.68119
Kirkpatrick, David; Snoeyink, Jack
14
1995
Tight lower bounds for probabilistic solitude verification on anonymous rings. Zbl 0806.68038
Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David
2
1994
Algorithms for degree constrained graph factors of minimum deficiency. Zbl 0764.68118
Hell, P.; Kirkpatrick, D. G.
16
1993
Computing the intersection-depth to polyhedra. Zbl 0797.68162
Dobkin, David; Hershberger, John; Kirkpatrick, David; Suri, Subhash
15
1993
Finding extrema with unary predicates. Zbl 0801.68078
Gao, Feng; Guibas, Leonidas J.; Kirkpatrick, David G.; Laaser, William T.; Saxe, James
1
1993
Quantitative Steinitz’s theorems with applications to multifingered grasping. Zbl 0747.52004
Kirkpatrick, David; Mishra, Bhubaneswar; Yap, Chee-Keng
5
1992
Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures. Zbl 0753.68092
Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E.
3
1992
Determining the separation of preprocessed polyhedra – A unified approach. Zbl 0765.68205
Dobkin, David P.; Kirkpatrick, David G.
30
1990
A simple existence criterion for \((g<f)\)-factors. Zbl 0723.05101
Heinrich, Katherine; Hell, Pavol; Kirkpatrick, David G.; Liu, Guizhen
18
1990
Parallel recognition of complement reducible graphs and cotree construction. Zbl 0707.68039
Kirkpatrick, D. G.; Przytycka, T.
5
1990
Parallel algorithms for fractional and maximal independent sets in planar graphs. Zbl 0699.68086
Dadoun, N.; Kirkpatrick, D. G.
4
1990
Finding extrema with unary predicates. Zbl 0819.68062
Kirkpatrick, David G.; Gao, Feng
1
1990
A simple parallel tree contraction algorithm. Zbl 0681.68085
Abrahamson, K.; Dadoun, N.; Kirkpatrick, D. G.; Przytycka, T.
47
1989
Parallel construction of subdivision hierarchies. Zbl 0678.68056
Dadoun, N.; Kirkpatrick, D. G.
7
1989
The bit complexity of randomized leader election on a ring. Zbl 0674.68029
Abrahamson, Karl; Adler, Andrew; Gelbart, Rachel; Higham, Lisa; Kirkpatrick, David
4
1989
Randomized function evaluation on a ring. Zbl 0703.68057
Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David
3
1989
Weighted visibility graphs of bars and related flow problems. (Extended abstract). Zbl 0765.68159
Kirkpatrick, David G.; Wismath, Stephen K.
3
1989
On restricted two-factors. Zbl 0672.05065
Hell, Pavol; Kirkpatrick, David; Kratochvíl, Jan; Kříž, Igor
13
1988
Addition requirements for matrix and transposed matrix products. Zbl 0653.65032
Kaminski, Michael; Kirkpatrick, David G.; Bshouty, Nader H.
8
1988
Establishing order in planar subdivisions. Zbl 0663.68053
Kirkpatrick, David G.
3
1988
The ultimate planar convex hull algorithm ? Zbl 0589.68035
Kirkpatrick, David G.; Seidel, Raimund
64
1986
Packings by complete bipartite graphs. Zbl 0597.05050
Hell, P.; Kirkpatrick, D. G.
21
1986
A note on f-factors in directed and undirected multigraphs. Zbl 0594.05053
Fraisse, Pierre; Hell, Pavol; Kirkpatrick, David G.
2
1986
A linear algorithm for determining the separation of convex polyhedra. Zbl 0577.52004
Dobkin, David P.; Kirkpatrick, David G.
35
1985
Alphabetic minimax trees. Zbl 0565.94025
Kirkpatrick, David G.; Klawe, Maria M.
5
1985
Some graph-colouring theorems with applications to generalized connection networks. Zbl 0572.05027
Kirkpatrick, David G.; Klawe, Maria; Pippenger, Nicholas
2
1985
Packings by cliques and by finite families of graphs. Zbl 0582.05046
Hell, P.; Kirkpatrick, D. G.
26
1984
Upper bounds for sorting integers on random access machines. Zbl 0533.68046
Kirkpatrick, David; Reisch, Stefan
17
1984
Optimal search in planar subdivisions. Zbl 0501.68034
Kirkpatrick, David
141
1983
On the shape of a set of points in the plane. Zbl 0512.52001
Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund
74
1983
On the complexity of general graph factor problems. Zbl 0525.68023
Kirkpatrick, D. G.; Hell, P.
67
1983
Fast detection of polyhedral intersection. Zbl 0553.68033
Dobkin, David P.; Kirkpatrick, David G.
35
1983
Families of recursively defined perfect graphs. Zbl 0576.05023
Corneil, D. G.; Kirkpatrick, D. G.
8
1983
Dynamic Voronoi diagrams. Zbl 0516.94030
Gowda, Ihor G.; Kirkpatrick, David G.; Lee, Der Tsai; Naamad, Amnon
5
1983
On pseudosimilarity in trees. Zbl 0536.05056
Kirkpatrick, D. G.; Klawe, M. M.; Corneil, D. G.
4
1983
Polygonal intersection searching. Zbl 0486.68051
Edelsbrunner, H.; Maurer, H. A.; Kirkpatrick, D. G.
12
1982
Fast detection of polyhedral intersections. Zbl 0494.68056
Dobkin, David P.; Kirkpatrick, David G.
4
1982
The shape of a set of points in the plane. Zbl 0537.68091
Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R.
2
1982
A time-space tradeoff for sorting on non-oblivious machines. Zbl 0462.68011
Borodin, Allan; Fischer, Michael J.; Kirkpatrick, David G.; Lynch, Nancy A.; Tompa, Martin
15
1981
On generalized matching problems. Zbl 0454.68077
Hell, P.; Kirkpatrick, D. G.
13
1981
A unified lower bound for selection and set partitioning problems. Zbl 0454.68076
Kirkpatrick, David G.
12
1981
Scheduling, matching, and coloring. Zbl 0474.05054
Hell, P.; Kirkpatrick, D. G.
5
1981
Forest embeddings in regular graphs of large girth. Zbl 0394.05016
Kirkpatrick, D. G.; Corneil, D. G.
2
1981
A note on Delaunay and optimal triangulations. Zbl 0458.05011
Kirkpatrick, David G.
15
1980
A theoretical analysis of various heuristics for the graph isomorphism problem. Zbl 0451.05043
Corneil, D. G.; Kirkpatrick, D. G.
8
1980
Generalized notions of pseudo-similarity in graphs. Zbl 0461.05045
Corneil, D. G.; Kirkpatrick, D. G.; Klawe, M. M.
1
1980
On the completeness of a generalized matching problem. Zbl 1282.68182
Kirkpatrick, David G.; Hell, Pavol
57
1978
Determining graph properties from matrix representations. Zbl 0358.68060
Kirkpatrick, David
4
1974
On the additions necessary to compute certain functions. Zbl 0356.65011
Kirkpatrick, David
1
1972
all top 5

Cited by 1,450 Authors

29 Kirkpatrick, David G.
20 Bose, Prosenjit K.
20 Chazelle, Bernard
20 Edelsbrunner, Herbert
20 Sharir, Micha
15 Guibas, Leonidas John
13 Smid, Michiel H. M.
13 Speckmann, Bettina
12 Hershberger, John E.
11 Aichholzer, Oswin
11 Durocher, Stephane
11 Goodrich, Michael Truman
10 de Berg, Mark Theodoor
9 Hell, Pavol
9 Snoeyink, Jack Scott
9 Suri, Subhash
9 Wang, Haitao
8 Chen, Danny Ziyi
8 Cueto, Elias
8 Hagerup, Torben
8 Maheshwari, Anil
8 Tóth, Csaba D.
7 Agarwal, Pankaj Kumar
7 Barequet, Gill
7 Carmi, Paz
7 Chan, Timothy Moon-Yew
7 da Fonseca, Guilherme Dias
7 Dobkin, David P.
7 Lingas, Andrzej
7 Liu, Guizhen
7 Rote, Günter
7 Souvaine, Diane L.
7 Toussaint, Godfried T.
7 Urrutia Galicia, Jorge L.
7 Welzl, Emo
6 Ahn, Hee-Kap
6 Angelopoulos, Spyros
6 Bereg, Sergey N.
6 Cheong, Otfried
6 Corneil, Derek Gordon
6 Doblaré, Manuel
6 Ghodsi, Mohammad
6 Hackl, Thomas
6 Hurtado, Ferran
6 Kano, Mikio
6 Kaplan, Haim
6 Lonc, Zbigniew
6 López-Ortiz, Alejandro
6 Matoušek, Jiří
6 Mitchell, Joseph S. B.
6 Raman, Venkatesh
6 Treglown, Andrew
5 Aggarwal, Alok
5 Bar-Noy, Amotz
5 Biniaz, Ahmad
5 Cabello, Sergio
5 Dickerson, Matthew T.
5 Diks, Krzysztof
5 Dumitrescu, Adrian
5 Eppstein, David Arthur
5 Fernau, Henning
5 Katz, Matthew J.
5 Korman, Matias
5 Langerman, Stefan
5 Levcopoulos, Christos
5 Liotta, Giuseppe
5 Lubiw, Anna
5 Mount, David M.
5 Orden, David
5 Peleg, David
5 Pilz, Alexander
5 Preparata, Franco P.
5 Przytycka, Teresa M.
5 Satti, Srinivasa Rao
4 Abam, Mohammad Ali
4 Aronov, Boris
4 Aurenhammer, Franz
4 Buchin, Kevin
4 Chakraborty, Sankardeep
4 Cheng, Siu-Wing
4 De, Minati
4 Devillers, Olivier
4 Dey, Tamal Krishna
4 Díaz, Josep
4 Feng, Qilong
4 Gagie, Travis
4 Han, Yijie
4 Hartvigsen, David B.
4 Hassin, Refael
4 He, Xin
4 Hsieh, Sun-Yuan
4 Kang, Liying
4 Krakovski, Roi
4 Kranakis, Evangelos Konstantinou
4 Kumar, Neeraj
4 Llanas, Bernardo
4 Löffler, Maarten
4 Masuyama, Shigeru
4 Mehrabi, Saeed
4 Morin, Pat
...and 1,350 more Authors
all top 5

Cited in 156 Serials

119 Computational Geometry
80 Algorithmica
79 Discrete Applied Mathematics
76 Theoretical Computer Science
63 Information Processing Letters
63 Discrete & Computational Geometry
32 Discrete Mathematics
26 International Journal of Computational Geometry & Applications
17 Journal of Computer and System Sciences
16 Graphs and Combinatorics
13 Journal of Combinatorial Theory. Series B
12 BIT
10 Information and Computation
10 European Journal of Operational Research
9 Journal of Combinatorial Optimization
8 Computer Aided Geometric Design
8 Journal of Discrete Algorithms
7 SIAM Journal on Discrete Mathematics
6 Acta Informatica
6 Computers & Mathematics with Applications
6 Theory of Computing Systems
5 Computer Methods in Applied Mechanics and Engineering
5 Journal of Graph Theory
5 SIAM Journal on Computing
5 European Journal of Combinatorics
5 Operations Research Letters
4 Artificial Intelligence
4 Journal of Computational Physics
4 Applied Mathematics and Computation
4 Computing
4 International Journal for Numerical Methods in Engineering
4 Networks
4 Journal of Symbolic Computation
4 Computers & Operations Research
4 International Journal of Computer Mathematics
4 Combinatorics, Probability and Computing
4 Discrete Optimization
4 Algorithms
3 Information Sciences
3 Journal of Combinatorial Theory. Series A
3 Journal of Robotic Systems
3 International Journal of Foundations of Computer Science
3 Pattern Recognition
3 Distributed Computing
3 Mathematical Programming. Series A. Series B
3 The Electronic Journal of Combinatorics
3 Journal of Graph Algorithms and Applications
3 Optimization Letters
3 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
2 International Journal of General Systems
2 Physica A
2 Automatica
2 Journal of Computational and Applied Mathematics
2 Journal of Soviet Mathematics
2 Mathematics of Operations Research
2 Transactions of the American Mathematical Society
2 SIAM Journal on Algebraic and Discrete Methods
2 Combinatorica
2 Acta Mathematicae Applicatae Sinica. English Series
2 Computational Statistics
2 Expositiones Mathematicae
2 Journal of Mathematical Imaging and Vision
2 Computational Complexity
2 Mathematical Problems in Engineering
2 International Journal of Shape Modeling
2 Parallel Algorithms and Applications
2 Journal of Scheduling
2 Archives of Computational Methods in Engineering
2 Journal of Zhejiang University. Science A
2 Acta Universitatis Sapientiae. Informatica
2 Journal of Theoretical Biology
2 Computer Science Review
1 Computers and Fluids
1 International Journal of Mathematical Education in Science and Technology
1 Journal of Fluid Mechanics
1 Journal of Mathematical Analysis and Applications
1 Journal of Mathematical Physics
1 Journal of Statistical Physics
1 Mathematical Methods in the Applied Sciences
1 Mathematics of Computation
1 Advances in Mathematics
1 Biometrical Journal
1 Geometriae Dedicata
1 International Journal of Computer & Information Sciences
1 Journal of the American Statistical Association
1 Journal of Geometry
1 Journal of Multivariate Analysis
1 Mathematica Slovaca
1 Mathematical Systems Theory
1 Monatshefte für Mathematik
1 Proceedings of the American Mathematical Society
1 Programming and Computer Software
1 Semigroup Forum
1 Studies in Applied Mathematics
1 Advances in Applied Mathematics
1 Applied Numerical Mathematics
1 Order
1 Optimization
1 ACM Transactions on Graphics
1 Journal of Complexity
...and 56 more Serials
all top 5

Cited in 41 Fields

632 Computer science (68-XX)
300 Combinatorics (05-XX)
123 Convex and discrete geometry (52-XX)
113 Numerical analysis (65-XX)
97 Operations research, mathematical programming (90-XX)
19 Geometry (51-XX)
14 Statistics (62-XX)
13 Probability theory and stochastic processes (60-XX)
13 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
11 Information and communication theory, circuits (94-XX)
10 Fluid mechanics (76-XX)
9 Algebraic topology (55-XX)
9 Biology and other natural sciences (92-XX)
7 Mechanics of particles and systems (70-XX)
7 Mechanics of deformable solids (74-XX)
6 Manifolds and cell complexes (57-XX)
5 Order, lattices, ordered algebraic structures (06-XX)
4 Number theory (11-XX)
3 Mathematical logic and foundations (03-XX)
3 Group theory and generalizations (20-XX)
3 Measure and integration (28-XX)
3 Systems theory; control (93-XX)
2 Field theory and polynomials (12-XX)
2 Linear and multilinear algebra; matrix theory (15-XX)
2 Dynamical systems and ergodic theory (37-XX)
2 Statistical mechanics, structure of matter (82-XX)
1 General and overarching topics; collections (00-XX)
1 History and biography (01-XX)
1 Commutative algebra (13-XX)
1 Algebraic geometry (14-XX)
1 Real functions (26-XX)
1 Partial differential equations (35-XX)
1 Approximations and expansions (41-XX)
1 Abstract harmonic analysis (43-XX)
1 Functional analysis (46-XX)
1 Calculus of variations and optimal control; optimization (49-XX)
1 Differential geometry (53-XX)
1 General topology (54-XX)
1 Astronomy and astrophysics (85-XX)
1 Geophysics (86-XX)
1 Mathematics education (97-XX)

Citations by Year