Edit Profile (opens in new tab) Kirkpatrick, David G. Co-Author Distance Author ID: kirkpatrick.david-g Published as: Kirkpatrick, David; Kirkpatrick, David G.; Kirkpatrick, D. G.; Kirkpatrick, D. more...less Documents Indexed: 116 Publications since 1972, including 1 Additional arXiv Preprint 2 Contributions as Editor Co-Authors: 91 Co-Authors with 106 Joint Publications 3,382 Co-Co-Authors 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 Eriksson-Bique, Sylvester 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 Polishchuk, Valentin 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 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 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 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 Yang, Boting all top 5 Serials 9 Discrete & Computational Geometry 8 SIAM Journal on Computing 7 Computational Geometry 6 Journal of Algorithms 6 International Journal of Computational Geometry & Applications 4 Discrete Applied Mathematics 4 Theoretical Computer Science 4 Algorithmica 3 Discrete Mathematics 3 Information Processing Letters 2 IEEE Transactions on Information Theory 2 Journal of the Association for Computing Machinery 2 Journal of Combinatorial Theory. Series B 2 Journal of Computer and System Sciences 2 SIAM Journal on Algebraic and Discrete Methods 2 SIAM Journal on Discrete Mathematics 1 Networks 1 Annales Societatis Mathematicae Polonae. Series IV 1 Graphs and Combinatorics 1 Distributed Computing 1 Theory of Computing Systems 1 Natural Computing 1 ACM Transactions on Algorithms all top 5 Fields 96 Computer science (68-XX) 37 Combinatorics (05-XX) 13 Convex and discrete geometry (52-XX) 13 Numerical analysis (65-XX) 9 Operations research, mathematical programming (90-XX) 6 Information and communication theory, circuits (94-XX) 3 General and overarching topics; collections (00-XX) 3 Geometry (51-XX) 1 Mathematical logic and foundations (03-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Differential geometry (53-XX) 1 Probability theory and stochastic processes (60-XX) 1 Mechanics of particles and systems (70-XX) 1 Geophysics (86-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 99 Publications have been cited 1,452 times in 1,194 Documents Cited by ▼ Year ▼ Optimal search in planar subdivisions. Zbl 0501.68034 Kirkpatrick, David 171 1983 On the shape of a set of points in the plane. Zbl 0512.52001 Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund 107 1983 On the complexity of general graph factor problems. Zbl 0525.68023 Kirkpatrick, D. G.; Hell, P. 92 1983 Unit disk graph recognition is NP-hard. Zbl 0894.68099 Breu, Heinz; Kirkpatrick, David G. 80 1998 The ultimate planar convex hull algorithm ? Zbl 0589.68035 Kirkpatrick, David G.; Seidel, Raimund 74 1986 On the completeness of a generalized matching problem. Zbl 1282.68182 Kirkpatrick, David G.; Hell, Pavol 70 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. 32 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 24 1990 Upper bounds for sorting integers on random access machines. Zbl 0533.68046 Kirkpatrick, David; Reisch, Stefan 22 1984 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 On restricted two-factors. Zbl 0672.05065 Hell, Pavol; Kirkpatrick, David; Kratochvíl, Jan; Kříž, Igor 20 1988 Algorithms for degree constrained graph factors of minimum deficiency. Zbl 0764.68118 Hell, P.; Kirkpatrick, D. G. 19 1993 Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Zbl 1022.05078 Bose, Prosenjit; Kirkpatrick, David; Li, Zaiqing 19 2003 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 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 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 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 Parallel construction of subdivision hierarchies. Zbl 0678.68056 Dadoun, N.; Kirkpatrick, D. G. 9 1989 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 Families of recursively defined perfect graphs. Zbl 0576.05023 Corneil, D. G.; Kirkpatrick, D. G. 8 1983 A theoretical analysis of various heuristics for the graph isomorphism problem. Zbl 0451.05043 Corneil, D. G.; Kirkpatrick, D. G. 8 1980 Swapping colored tokens on graphs. Zbl 1451.68135 Yamanaka, Katsuhisa; Horiyama, Takashi; Kirkpatrick, David; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei; Uno, Yushi 8 2015 Fast detection of polyhedral intersections. Zbl 0494.68056 Dobkin, David P.; Kirkpatrick, David G. 7 1982 Dynamic Voronoi diagrams. Zbl 0516.94030 Gowda, Ihor G.; Kirkpatrick, David G.; Lee, Der Tsai; Naamad, Amnon 7 1983 Equitable subdivisions within polygonal regions. Zbl 1098.65023 Bereg, Sergey; Bose, Prosenjit; Kirkpatrick, David 7 2006 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 Scheduling, matching, and coloring. Zbl 0474.05054 Hell, P.; Kirkpatrick, D. G. 6 1981 Finding nearest larger neighbors. A case study in algorithm design and analysis. Zbl 1258.68178 Asano, Tetsuo; Bereg, Sergey; Kirkpatrick, David 6 2009 Quantitative Steinitz’s theorems with applications to multifingered grasping. Zbl 0747.52004 Kirkpatrick, David; Mishra, Bhubaneswar; Yap, Chee-Keng 6 1992 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 Linear-time certifying algorithms for near-graphical sequences. Zbl 1185.05135 Hell, Pavol; Kirkpatrick, David 5 2009 Alphabetic minimax trees. Zbl 0565.94025 Kirkpatrick, David G.; Klawe, Maria M. 5 1985 Simplifying analyses of chemical reaction networks for approximate majority. Zbl 1495.68071 Condon, Anne; Hajiaghayi, Monir; Kirkpatrick, David; Maňuch, Ján 5 2017 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 Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. Zbl 1318.68059 Evans, William; Kirkpatrick, David 5 2004 Establishing order in planar subdivisions. Zbl 0663.68053 Kirkpatrick, David G. 4 1988 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 Determining graph properties from matrix representations. Zbl 0358.68060 Kirkpatrick, David 4 1974 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 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 On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Zbl 1131.68316 Durocher, Stephane; Kirkpatrick, David; Narayanan, Lata 3 2008 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 Constrained equitable \(3\)-cuttings. Zbl 1179.52003 Bespamyatnikh, Sergei; Kirkpatrick, David 3 2003 A complete approximation algorithm for shortest bounded-curvature paths. Zbl 1183.68741 Backer, Jonathan; Kirkpatrick, David 3 2008 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 Optimal algorithm for probabilistic solitude detection on anonymous rings. Zbl 0873.68080 Higham, Lisa; Kirkpatrick, David; Abrahamson, Karl; Adler, Andrew 3 1997 Finding extrema with unary predicates. Zbl 0801.68078 Gao, Feng; Guibas, Leonidas J.; Kirkpatrick, David G.; Laaser, William T.; Saxe, James 3 1993 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 Separation sensitive kinetic separation structures for convex polygons. Zbl 0990.68164 Kirkpatrick, David; Speckmann, Bettina 3 2001 Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\). Zbl 1394.68185 Kirkpatrick, David 3 2013 The shape of a set of points in the plane. Zbl 0537.68091 Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R. 2 1982 Parallel construction of binary trees with near optimal weighted path length. Zbl 0836.68053 Kirkpatrick, D. G.; Przytycka, T. 2 1996 Finding curvature-constrained paths that avoid polygonal obstacles. Zbl 1221.68291 Backer, Jonathan; Kirkpatrick, David 2 2007 Some graph-colouring theorems with applications to generalized connection networks. Zbl 0572.05027 Kirkpatrick, David G.; Klawe, Maria; Pippenger, Nicholas 2 1985 A note on f-factors in directed and undirected multigraphs. Zbl 0594.05053 Fraisse, Pierre; Hell, Pavol; Kirkpatrick, David G. 2 1986 Forest embeddings in regular graphs of large girth. Zbl 0394.05016 Kirkpatrick, D. G.; Corneil, D. G. 2 1981 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 Curvature-bounded traversals of narrow corridors. Zbl 1380.68381 Bereg, Sergey; Kirkpatrick, David 2 2005 Lower bounds on average-case delay for video-on-demand broadcast protocols. Zbl 1302.68029 Tseng, Wei-Lung Dustin; Kirkpatrick, David 2 2007 Computing common tangents without a separating line. Zbl 1502.68328 Kirkpatrick, David; Snoeyink, Jack 2 1995 Computing constrained shortest segments: Butterfly wingspans in logarithmic time. Zbl 1020.52013 Kirkpatrick, David; Snoeyink, Jack 1 1999 On the spanning ratio of Gabriel graphs and \(\beta\)-skeletons. Zbl 1059.68145 Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David 1 2002 On the additions necessary to compute certain functions. Zbl 0356.65011 Kirkpatrick, David 1 1972 Generalized notions of pseudo-similarity in graphs. Zbl 0461.05045 Corneil, D. G.; Kirkpatrick, D. G.; Klawe, M. M. 1 1980 Finding extrema with unary predicates. Zbl 0819.68062 Kirkpatrick, David G.; Gao, Feng 1 1990 Approximating barrier resilience for arrangements of non-identical disk sensors. Zbl 1351.68196 Chan, David Yu Cheng; Kirkpatrick, David 1 2013 Minimizing interference potential among moving entities. Zbl 1432.68502 Busto, Daniel; Evans, William; Kirkpatrick, David 1 2019 Approximate majority analyses using tri-molecular chemical reaction networks. Zbl 07802747 Condon, Anne; Hajiaghayi, Monir; Kirkpatrick, David; Maňuch, Ján 1 2020 Approximate majority analyses using tri-molecular chemical reaction networks. Zbl 07802747 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 5 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 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 Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\). Zbl 1394.68185 Kirkpatrick, David 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 Finding curvature-constrained paths that avoid polygonal obstacles. Zbl 1221.68291 Backer, Jonathan; Kirkpatrick, David 2 2007 Lower bounds on average-case delay for video-on-demand broadcast protocols. Zbl 1302.68029 Tseng, Wei-Lung Dustin; 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 19 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 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. 80 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 24 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 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 20 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 The ultimate planar convex hull algorithm ? Zbl 0589.68035 Kirkpatrick, David G.; Seidel, Raimund 74 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. 32 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 171 1983 On the shape of a set of points in the plane. Zbl 0512.52001 Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund 107 1983 On the complexity of general graph factor problems. Zbl 0525.68023 Kirkpatrick, D. G.; Hell, P. 92 1983 Fast detection of polyhedral intersection. Zbl 0553.68033 Dobkin, David P.; Kirkpatrick, David G. 38 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 7 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. 6 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. 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 70 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 cited Publications top 5 cited Publications all top 5 Cited by 1,825 Authors 31 Kirkpatrick, David G. 26 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 Carmi, Paz 7 da Fonseca, Guilherme Dias 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 Liu, Guizhen 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 Biniaz, Ahmad 6 Cabello, Sergio 6 Cheong, Otfried 6 Corneil, Derek Gordon 6 Díaz, Josep 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 Liotta, Giuseppe 6 Löffler, Maarten 6 Lubiw, Anna 6 Matoušek, Jiří 6 Mehrabi, Saeed 6 Orden, David 6 Pantziou, Grammati E. 6 Saitoh, Toshiki 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 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 Pilz, Alexander 5 Przytycka, Teresa M. 5 Roeloffzen, Marcel 5 Sack, Jörg-Rüdiger ...and 1,725 more Authors all top 5 Cited in 178 Serials 128 Computational Geometry 86 Algorithmica 85 Discrete Applied Mathematics 82 Theoretical Computer Science 68 Discrete & Computational Geometry 63 Information Processing Letters 35 Discrete Mathematics 29 International Journal of Computational Geometry & Applications 20 Journal of Computer and System Sciences 18 Graphs and Combinatorics 14 Journal of Combinatorial Theory. Series B 14 European Journal of Operational Research 12 BIT 12 Journal of Combinatorial Optimization 11 Information and Computation 10 SIAM Journal on Computing 9 Computer Aided Geometric Design 8 SIAM Journal on Discrete Mathematics 8 Journal of Discrete Algorithms 7 Acta Informatica 7 Computers & Mathematics with Applications 7 Journal of Graph Theory 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 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 Scientific Computing 2 Random Structures & Algorithms 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 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 1 Journal of the American Statistical Association 1 Journal of Geometry ...and 78 more Serials all top 5 Cited in 43 Fields 801 Computer science (68-XX) 365 Combinatorics (05-XX) 145 Convex and discrete geometry (52-XX) 120 Numerical analysis (65-XX) 119 Operations research, mathematical programming (90-XX) 23 Statistics (62-XX) 21 Geometry (51-XX) 18 Biology and other natural sciences (92-XX) 15 Probability theory and stochastic processes (60-XX) 15 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Algebraic topology (55-XX) 14 Information and communication theory, circuits (94-XX) 12 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) 2 Field theory and polynomials (12-XX) 2 Partial differential equations (35-XX) 2 Approximations and expansions (41-XX) 2 Calculus of variations and optimal control; optimization (49-XX) 2 Differential geometry (53-XX) 2 General topology (54-XX) 2 Geophysics (86-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 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