×

Kirkpatrick, David G.

Author ID: kirkpatrick.david-g Recent zbMATH articles by "Kirkpatrick, David G."
Published as: Kirkpatrick, David; Kirkpatrick, David G.; Kirkpatrick, D. G.; Kirkpatrick, D.
all top 5

Co-Authors

11 single-authored
12 Hell, Pavol
11 Evans, William S.
8 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 Condon, Anne E.
2 Devroye, Luc P. J. A.
2 Gao, Feng
2 Hajiaghayi, Monir
2 Horiyama, Takashi
2 Keil, J. Mark
2 Löffler, Maarten
2 Maňuch, Ján
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 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 Heinrich, Katherine
1 Hershberger, John E.
1 Kaminski, Michael
1 Kedem, Zvi Meir
1 Keil, Mark J.
1 Kettner, Lutz
1 Kostitsyna, Irina
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 Maurer, Hermann A.
1 McAllister, Michael
1 Mishra, Bhubaneswar
1 Naamad, Amnon
1 Nakagawa, Kotaro
1 Narayanan, Lata
1 Navarra, Alfredo
1 Polishchuk, Valentin
1 Prencipe, Giuseppe
1 Rangan, Chandrasekharan Pandu
1 Reddy, K. Madhukar
1 Reisch, Stefan
1 Ries, Christoph
1 Santoro, Nicola
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 Yang, Boting

Publications by Year

Citations contained in zbMATH Open

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

Cited by 1,873 Authors

31 Kirkpatrick, David G.
27 Bose, Prosenjit K.
22 Edelsbrunner, Herbert
22 Sharir, Micha
21 Chazelle, Bernard
16 Durocher, Stephane
16 Goodrich, Michael Truman
16 Smid, Michiel H. M.
15 Guibas, Leonidas John
15 Hershberger, John E.
14 Speckmann, Bettina
13 Tóth, Csaba D.
12 Aichholzer, Oswin
12 de Berg, Mark Theodoor
12 Raman, Venkatesh
12 Wang, Haitao
11 Snoeyink, Jack Scott
11 Suri, Subhash
10 Ahn, Hee-Kap
10 Angelopoulos, Spyros
10 Barequet, Gill
10 Dumitrescu, Adrian
10 Maheshwari, Anil
9 Hell, Pavol
9 Urrutia Galicia, Jorge L.
8 Agarwal, Pankaj Kumar
8 Bereg, Sergey N.
8 Chan, Timothy Moon-Yew
8 Chen, Danny Ziyi
8 Cueto, Elias
8 Hagerup, Torben
8 Lingas, Andrzej
8 Lonc, Zbigniew
8 Olariu, Stephan
8 Peleg, David
8 Souvaine, Diane L.
7 Bar-Noy, Amotz
7 Biniaz, Ahmad
7 Carmi, Paz
7 da Fonseca, Guilherme Dias
7 Díaz, Josep
7 Dickerson, Matthew T.
7 Dobkin, David P.
7 Fernau, Henning
7 Ghodsi, Mohammad
7 Katz, Matthew J.
7 Korman, Matias
7 Levcopoulos, Christos
7 Liotta, Giuseppe
7 Liu, Guizhen
7 Löffler, Maarten
7 López-Ortiz, Alejandro
7 Mitchell, Joseph S. B.
7 Preparata, Franco P.
7 Rote, Günter
7 Satti, Srinivasa Rao
7 Tamassia, Roberto
7 Toussaint, Godfried T.
7 Welzl, Emo
6 Cabello, Sergio
6 Cheong, Otfried
6 Corneil, Derek Gordon
6 Doblaré, Manuel
6 Eppstein, David Arthur
6 Hackl, Thomas
6 Han, Jie
6 Hurtado, Ferran
6 Kano, Mikio
6 Kaplan, Haim
6 Langerman, Stefan
6 Lubiw, Anna
6 Matoušek, Jiří
6 Mehrabi, Saeed
6 Morin, Pat
6 Orden, David
6 Pantziou, Grammati E.
6 Saitoh, Toshiki
6 Schulz, André
6 Treglown, Andrew
5 Aggarwal, Alok
5 Aurenhammer, Franz
5 Bhattacharya, Binay Kumar
5 Buchin, Kevin
5 Chakraborty, Sankardeep
5 Damaschke, Peter
5 Devillers, Olivier
5 Diks, Krzysztof
5 Dürr, Christoph
5 Gagie, Travis
5 Han, Yijie
5 Hartvigsen, David B.
5 He, Xin
5 Kranakis, Evangelos Konstantinou
5 Lee, Der-Tsai
5 Miltzow, Tillmann
5 Mokeev, Dmitriĭ Borisovich
5 Mount, David M.
5 Mulzer, Wolfgang Johann Heinrich
5 Palios, Leonidas
5 Paulusma, Daniël
...and 1,773 more Authors
all top 5

Cited in 183 Serials

129 Computational Geometry
86 Discrete Applied Mathematics
86 Algorithmica
83 Theoretical Computer Science
69 Discrete & Computational Geometry
64 Information Processing Letters
35 Discrete Mathematics
29 International Journal of Computational Geometry & Applications
21 Journal of Computer and System Sciences
18 Graphs and Combinatorics
15 Journal of Combinatorial Theory. Series B
14 European Journal of Operational Research
13 Journal of Combinatorial Optimization
12 BIT
12 Information and Computation
10 SIAM Journal on Computing
9 Computer Aided Geometric Design
9 SIAM Journal on Discrete Mathematics
8 Computers & Mathematics with Applications
8 Journal of Graph Theory
8 Journal of Discrete Algorithms
7 Acta Informatica
7 Theory of Computing Systems
6 Applied Mathematics and Computation
5 Artificial Intelligence
5 Computer Methods in Applied Mechanics and Engineering
5 Networks
5 European Journal of Combinatorics
5 Operations Research Letters
5 Computers & Operations Research
5 The Electronic Journal of Combinatorics
5 Optimization Letters
4 Journal of Computational Physics
4 Computing
4 International Journal for Numerical Methods in Engineering
4 Journal of Combinatorial Theory. Series A
4 Combinatorica
4 Journal of Symbolic Computation
4 International Journal of Computer Mathematics
4 Distributed Computing
4 Mathematical Programming. Series A. Series B
4 Combinatorics, Probability and Computing
4 Journal of Graph Algorithms and Applications
4 Discrete Optimization
4 Algorithms
4 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
3 Computers and Fluids
3 Information Sciences
3 Journal of Robotic Systems
3 Journal of Scientific Computing
3 Random Structures & Algorithms
3 International Journal of Foundations of Computer Science
3 Pattern Recognition
3 Expositiones Mathematicae
3 Journal of Mathematical Imaging and Vision
3 Journal of Scheduling
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 Advances in Applied Mathematics
2 SIAM Journal on Algebraic and Discrete Methods
2 Acta Mathematicae Applicatae Sinica. English Series
2 Journal of Complexity
2 Journal of Global Optimization
2 Computational Statistics
2 Computational Statistics and Data Analysis
2 Computational Complexity
2 Journal of Mathematical Chemistry
2 Mathematical Problems in Engineering
2 International Journal of Shape Modeling
2 Parallel Algorithms and Applications
2 Archives of Computational Methods in Engineering
2 SIAM Journal on Applied Dynamical Systems
2 Journal of Zhejiang University. Science A
2 The Annals of Applied Statistics
2 Acta Universitatis Sapientiae. Informatica
2 ACM Transactions on Algorithms
2 Journal of Theoretical Biology
2 Computer Science Review
1 Computer Physics Communications
1 International Journal of Mathematical Education in Science and Technology
1 Inverse Problems
1 Journal of Fluid Mechanics
1 Journal of Mathematical Analysis and Applications
1 Journal of Mathematical Physics
1 Journal of Statistical Physics
1 Linear and Multilinear Algebra
1 Mathematical Methods in the Applied Sciences
1 Mathematics of Computation
1 Advances in Mathematics
1 The Annals of Statistics
1 Biometrical Journal
1 Bulletin of the London Mathematical Society
1 Geometriae Dedicata
1 International Journal of Computer & Information Sciences
1 International Journal of Game Theory
...and 83 more Serials
all top 5

Cited in 43 Fields

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

Citations by Year