Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarDavid G. Kirkpatrick
Person information
- affiliation: University of British Columbia, Vancouver, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2019
[c86]Daniel Busto, William S. Evans, David G. Kirkpatrick:
Minimizing Interference Potential Among Moving Entities. SODA 2019: 2400-2418- 2018
- [j73]Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno:
Swapping colored tokens on graphs. Theor. Comput. Sci. 729: 1-10 (2018) - [i5]Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno:
Swapping Colored Tokens on Graphs. CoRR abs/1803.06816 (2018) - 2017
- [c85]Ziyuan Gao, David G. Kirkpatrick, Christoph Ries, Hans Ulrich Simon, Sandra Zilles:
Preference-based Teaching of Unions of Geometric Objects. ALT 2017: 185-207 - [c84]Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, Ján Manuch:
Simplifying Analyses of Chemical Reaction Networks for Approximate Majority. DNA 2017: 188-209 - [c83]Toshiki Saitoh, David G. Kirkpatrick:
Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals. WALCOM 2017: 320-332 - 2016
- [j72]William S. Evans, David G. Kirkpatrick, Maarten Löffler, Frank Staals:
Minimizing Co-location Potential of Moving Entities. SIAM J. Comput. 45(5): 1870-1893 (2016) - [c82]Ashwin Gopinath, David G. Kirkpatrick, Paul W. K. Rothemund, Chris Thachuk:
Progressive Alignment of Shapes. CCCG 2016: 230-236 - [c81]
- [i4]David G. Kirkpatrick, Paul Liu:
Characterizing minimum-length coordinated motions for two discs. CoRR abs/1607.04005 (2016) - 2015
- [j71]David G. Kirkpatrick:
An O(lg lg OPT)-Approximation Algorithm for Multi-guarding Galleries. Discrete & Computational Geometry 53(2): 327-343 (2015) - [c80]Katsuhisa Yamanaka, Takashi Horiyama, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno:
Swapping Colored Tokens on Graphs. WADS 2015: 619-628 - 2014
- [j70]David G. Kirkpatrick, Boting Yang, Sandra Zilles:
A Polynomial-Time Algorithm for Computing the Resilience of Arrangements of Ray Sensors. Int. J. Comput. Geometry Appl. 24(3): 225-236 (2014) - [j69]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
Computational Aspects of M.C. Escher's Ribbon Patterns. Theory Comput. Syst. 54(4): 640-658 (2014) - [j68]David Yu Cheng Chan, David G. Kirkpatrick:
Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilience. Theor. Comput. Sci. 553: 74-90 (2014) - [c79]Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. MFCS (2) 2014: 45-56 - [i3]Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. Electronic Colloquium on Computational Complexity (ECCC) 21: 71 (2014) - 2013
- [c78]David G. Kirkpatrick:
Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50. Space-Efficient Data Structures, Streams, and Algorithms 2013: 61-76 - [c77]
- [c76]William S. Evans, David G. Kirkpatrick, Maarten Löffler, Frank Staals:
Competitive query strategies for minimising the ply of the potential locations of moving points. Symposium on Computational Geometry 2013: 155-164 - [c75]Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk:
On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case. JCDCGG 2013: 44-64 - [c74]Tetsuo Asano, David G. Kirkpatrick:
Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems. WADS 2013: 61-72 - 2012
- [j67]
- [j66]David G. Kirkpatrick:
Guest Editor's Foreword. Discrete & Computational Geometry 47(4): 659-660 (2012) - [c73]David Yu Cheng Chan, David G. Kirkpatrick:
Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors. ALGOSENSORS 2012: 42-53 - [c72]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns. FUN 2012: 198-209 - [i2]Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk:
Discrete Dubins Paths. CoRR abs/1211.2365 (2012) - 2011
- [j65]James King, David G. Kirkpatrick:
Improved Approximation for Guarding Simple Galleries from the Perimeter. Discrete & Computational Geometry 46(2): 252-269 (2011) - [c71]Kuan-Chieh Robert Tseng, David G. Kirkpatrick:
On Barrier Resilience of Sensor Networks. ALGOSENSORS 2011: 130-144 - [c70]David G. Kirkpatrick, Irina Kostitsyna, Valentin Polishchuk:
Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning. CCCG 2011 - [c69]Victor Alvarez, David G. Kirkpatrick, Raimund Seidel:
Can Nearest Neighbor Searching Be Simple and Always Fast? ESA 2011: 82-92 - [c68]
- [c67]
- 2010
- [j64]Stephane Durocher, David G. Kirkpatrick, Lata Narayanan:
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Wireless Networks 16(1): 227-235 (2010) - [c66]Zohreh Jabbari, William S. Evans, David G. Kirkpatrick:
Multi-guard covers for polygonal regions. CCCG 2010: 5-8 - [c65]
- [e1]David G. Kirkpatrick, Joseph S. B. Mitchell:
Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010. ACM 2010, ISBN 978-1-4503-0016-2 [contents] - [i1]James King, David G. Kirkpatrick:
Improved Approximation for Guarding Simple Galleries from the Perimeter. CoRR abs/1001.4231 (2010)
2000 – 2009
- 2009
- [j63]Stephane Durocher, David G. Kirkpatrick:
The projection median of a set of points. Comput. Geom. 42(5): 364-375 (2009) - [j62]Pavol Hell, David G. Kirkpatrick:
Linear-time certifying algorithms for near-graphical sequences. Discrete Mathematics 309(18): 5703-5713 (2009) - [c64]Sergey Bereg, David G. Kirkpatrick:
Approximating Barrier Resilience in Wireless Sensor Networks. ALGOSENSORS 2009: 29-40 - [c63]Tetsuo Asano, Sergey Bereg, David G. Kirkpatrick:
Finding Nearest Larger Neighbors. Efficient Algorithms 2009: 249-260 - [c62]
- 2008
- [j61]Stephane Durocher, David G. Kirkpatrick:
Bounded-Velocity Approximation of Mobile Euclidean 2-Centres. Int. J. Comput. Geometry Appl. 18(3): 161-183 (2008) - [c61]Stephane Durocher, David G. Kirkpatrick, Lata Narayanan:
On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks. ICDCN 2008: 546-557 - [c60]Jonathan Backer, David G. Kirkpatrick:
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths. ISAAC 2008: 628-643 - 2007
- [c59]Jonathan Backer, David G. Kirkpatrick:
Finding curvature-constrained paths that avoid polygonal obstacles. Symposium on Computational Geometry 2007: 66-73 - [c58]Wei-Lung Dustin Tseng, David G. Kirkpatrick:
Lower bounds on average-case delay for video-on-demand broadcast protocols. SODA 2007: 834-842 - 2006
- [j60]Sergey Bereg, Prosenjit Bose, David G. Kirkpatrick:
Equitable subdivisions within polygonal regions. Comput. Geom. 34(1): 20-27 (2006) - [j59]Stephane Durocher, David G. Kirkpatrick:
The Steiner Centre of a Set of Points: Stability, Eccentricity, and Applications to Mobile Facility Location. Int. J. Comput. Geometry Appl. 16(4): 345-372 (2006) - [j58]Sergey Bereg, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Competitive Algorithms for Maintaining a Mobile Center. MONET 11(2): 177-186 (2006) - [j57]Prosenjit Bose, Luc Devroye, William S. Evans, David G. Kirkpatrick:
On the Spanning Ratio of Gabriel Graphs and beta-Skeletons. SIAM J. Discrete Math. 20(2): 412-427 (2006) - [j56]William S. Evans, David G. Kirkpatrick:
Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ. ACM Trans. Algorithms 2(4): 661-678 (2006) - [c57]
- [c56]Tetsuo Asano, David G. Kirkpatrick:
Distance Trisector Curves in Regular Convex Distance Me. ISVD 2006: 8-17 - 2005
- [j55]Daniel W. Archambault, William S. Evans, David G. Kirkpatrick:
Computing the Set of all the Distant Horizons of a Terrain. Int. J. Comput. Geometry Appl. 15(6): 547-564 (2005) - [c55]Stephane Durocher, David G. Kirkpatrick:
The Projection Median of a Set of Points in R2. CCCG 2005: 47-51 - [c54]Sergey Bereg, David G. Kirkpatrick:
Curvature-bounded traversals of narrow corridors. Symposium on Computational Geometry 2005: 278-287 - 2004
- [j54]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning. Discrete & Computational Geometry 31(1): 139-171 (2004) - [j53]William S. Evans, David G. Kirkpatrick:
Restructuring ordered binary trees. J. Algorithms 50(2): 168-193 (2004) - [c53]William S. Evans, Daniel W. Archambault, David G. Kirkpatrick:
Computing the set of all distant horizons of a terrain. CCCG 2004: 76-79 - [c52]Stephane Durocher, David G. Kirkpatrick:
The gaussian centre and the projection centre of a set of points in r3. CCCG 2004: 140-144 - [c51]William S. Evans, David G. Kirkpatrick:
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. SODA 2004: 1041-1049 - 2003
- [j52]Lutz Kettner, David G. Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, Fumihiko Takeuchi:
Tight degree bounds for pseudo-triangulations of points. Comput. Geom. 25(1-2): 3-12 (2003) - [j51]Prosenjit Bose, David G. Kirkpatrick, Zaiqing Li:
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Comput. Geom. 26(3): 209-219 (2003) - [c50]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Minimizing the trace length of a rod endpoint in the presence of polygonal obstacles is NP-hard. CCCG 2003: 10-13 - [c49]Stephane Durocher, David G. Kirkpatrick:
The Gaussian Centre of a Set of Mobile Points. CCCG 2003: 123-127 - 2002
- [j50]David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann:
Kinetic Collision Detection for Simple Polygons. Int. J. Comput. Geometry Appl. 12(1-2): 3-27 (2002) - [j49]Sergei Bespamyatnikh, Binay K. Bhattacharya, J. Mark Keil, David G. Kirkpatrick, Michael Segal:
Efficient algorithms for centers and medians in interval and circular-arc graphs. Networks 39(3): 144-152 (2002) - [c48]Stephane Durocher, David G. Kirkpatrick:
On the hardness of turn-angle-restricted rectilinear cycle cover problems. CCCG 2002: 13-16 - [c47]Francois Anton, David G. Kirkpatrick, Darka Mioc:
An exact algebraic predicate for maintaining the topology of the voronoi diagram for circles. CCCG 2002: 72-76 - [c46]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Pseudo approximation algorithms, with applications to optimal motion planning. Symposium on Computational Geometry 2002: 170-178 - [c45]David G. Kirkpatrick, Bettina Speckmann:
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. Symposium on Computational Geometry 2002: 179-188 - [c44]Sergei Bespamyatnikh, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Lower and Upper Bounds for Tracking Mobile Users. IFIP TCS 2002: 47-58 - [c43]
- [c42]Prosenjit Bose, Luc Devroye, William S. Evans, David G. Kirkpatrick:
On the Spanning Ratio of Gabriel Graphs and beta-skeletons. LATIN 2002: 479-493 - 2001
- [j48]William S. Evans, David G. Kirkpatrick, G. Townsend:
Right-Triangulated Irregular Networks. Algorithmica 30(2): 264-286 (2001) - [c41]Lutz Kettner, David G. Kirkpatrick, Bettina Speckmann:
Tight degree bounds for pseudo-triangulations of points. CCCG 2001: 117-120 - 2000
- [j47]Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. Discrete & Computational Geometry 24(4): 605-622 (2000) - [c40]
- [c39]David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann:
Kinetic collision detection for simple polygons. Symposium on Computational Geometry 2000: 322-330 - [c38]Sergei Bespamyatnikh, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Mobile facility location. DIAL-M 2000: 46-53 - [c37]Sergei Bespamyatnikh, Binay K. Bhattacharya, J. Mark Keil, David G. Kirkpatrick, Michael Segal:
Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs. ESA 2000: 100-111 - [c36]David G. Kirkpatrick, Bettina Speckmann:
Separation Sensitive Kinetic Separation Structures for Convex Polygons. JCDCG 2000: 222-236 - [c35]
1990 – 1999
- 1999
- [j46]David G. Kirkpatrick, Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time. Int. J. Comput. Geometry Appl. 9(1): 53-62 (1999) - [c34]
- [c33]Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. Symposium on Computational Geometry 1999: 49-58 - 1998
- [j45]Heinz Breu, David G. Kirkpatrick:
Unit disk graph recognition is NP-hard. Comput. Geom. 9(1-2): 3-24 (1998) - [j44]David G. Kirkpatrick, Madhukar K. Reddy, C. Pandu Rangan, Anand Srinivasan:
Partial and Perfect Path Covers of Cographs. Discrete Applied Mathematics 89(1-3): 143-153 (1998) - 1997
- [j43]Lisa Higham, David G. Kirkpatrick, Karl R. Abrahamson, Andrew Adler:
Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings. J. Algorithms 23(2): 291-328 (1997) - 1996
- [j42]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel Construction of Binary Trees with Near Optimal Weighted Path Lengt. Algorithmica 15(2): 172-192 (1996) - [j41]David G. Kirkpatrick, Stephen K. Wismath:
Determining Bar-representability for Ordered Weighted Graphs. Comput. Geom. 6: 99-122 (1996) - [j40]Pavol Hell, David G. Kirkpatrick, Brenda Li:
Rounding in Symmetric Matrices and Undirected Graphs. Discrete Applied Mathematics 70(1): 1-21 (1996) - [j39]Michael McAllister, David G. Kirkpatrick, Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. Discrete & Computational Geometry 15(1): 73-105 (1996) - [c32]Prosenjit Bose, William S. Evans, David G. Kirkpatrick, Michael McAllister, Jack Snoeyink:
Approximating Shortest Paths in Arrangements of Lines. CCCG 1996: 143-148 - [c31]Prosenjit Bose, David G. Kirkpatrick, Zaiqing Li:
Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain. CCCG 1996: 217-222 - [c30]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
d1-Optimal Motion for a Rod (Extended Abstract). Symposium on Computational Geometry 1996: 252-263 - 1995
- [j38]David G. Kirkpatrick, Jack Snoeyink:
Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation. Fundam. Inform. 22(4): 353-370 (1995) - [j37]Heinz Breu, Joseph Gil, David G. Kirkpatrick, Michael Werman:
Linear Time Euclidean Distance Algorithms. IEEE Trans. Pattern Anal. Mach. Intell. 17(5): 529-533 (1995) - [c29]Heinz Breu, David G. Kirkpatrick:
On the Complexity of Recognizing Intersection and Touching Graphs of Disks. Graph Drawing 1995: 88-98 - [c28]David G. Kirkpatrick, Jack Snoeyink:
Computing Common Tangents Without a Separating Line. WADS 1995: 183-193 - 1994
- [j36]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings. J. ACM 41(2): 277-310 (1994) - 1993
- [j35]David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri:
Computing the Intersection-Depth of Polyhedra. Algorithmica 9(6): 518-533 (1993) - [j34]Feng Gao, Leonidas J. Guibas, David G. Kirkpatrick, William T. Laaser, James B. Saxe:
Finding Extrema with Unary Predicates. Algorithmica 9(6): 591-600 (1993) - [j33]Pavol Hell, David G. Kirkpatrick:
Algorithms for Degree Constrained Graph Factors of Minimum Deficiency. J. Algorithms 14(1): 115-138 (1993) - [c27]David G. Kirkpatrick, Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time. CCCG 1993: 163-168 - [c26]David G. Kirkpatrick, Jack Snoeyink:
Tentative Prune-and-Search for Computing Voronoi Vertices. Symposium on Computational Geometry 1993: 133-142 - [c25]Michael McAllister, David G. Kirkpatrick, Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. FOCS 1993: 573-582 - 1992
- [j32]David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap:
Quantitative Steinitz's Theorems Applications to Multifingered Grasping. Discrete & Computational Geometry 7: 295-318 (1992) - [j31]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O (n log log n) Time with Simple Data Structures. Discrete & Computational Geometry 7: 329-346 (1992) - 1991
- [c24]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Probabilistic Leader Election on Rings of Known Size. WADS 1991: 481-495 - 1990
- [j30]Norm Dadoun, David G. Kirkpatrick:
Parallel algorithms for fractional and maximal independent sets in planar graphs. Discrete Applied Mathematics 27(1-2): 69-83 (1990) - [j29]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel recognition of complement reducible graphs and cotree construction. Discrete Applied Mathematics 29(1): 79-96 (1990) - [j28]Katherine Heinrich, Pavol Hell, David G. Kirkpatrick, Guizhen Liu:
A simple existence criterion for (g<f)- factors. Discrete Mathematics 85(3): 313-317 (1990) - [c23]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O(n log log n) Time with Simple Data-Structures. Symposium on Computational Geometry 1990: 34-43 - [c22]David P. Dobkin, David G. Kirkpatrick:
Determining the Separation of Preprocessed Polyhedra - A Unified Approach. ICALP 1990: 400-413 - [c21]David G. Kirkpatrick, Feng Gao:
Finding Extrema with Unary Predicates. SIGAL International Symposium on Algorithms 1990: 156-164 - [c20]David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri:
Implicitly Searching Convolutions and Computing Depth of Collision. SIGAL International Symposium on Algorithms 1990: 165-180 - [c19]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel Construction of near Optimal binary Trees. SPAA 1990: 234-243 - [c18]David G. Kirkpatrick, Teresa M. Przytycka:
An optimal parallel minimax tree algorithm. SPDP 1990: 293-300 - [c17]David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap:
Quantitative Steinitz's Theorems with Applications to Multifingered Grasping. STOC 1990: 341-351
1980 – 1989
- 1989
- [j27]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Randomized Function Evaluation on a Ring. Distributed Computing 3(3): 107-117 (1989) - [j26]Karl R. Abrahamson, Norm Dadoun, David G. Kirkpatrick, Teresa M. Przytycka:
A Simple Parallel Tree Contraction Algorithm. J. Algorithms 10(2): 287-302 (1989) - [j25]Norm Dadoun, David G. Kirkpatrick:
Parallel Construction of Subdivision Hierarchies. J. Comput. Syst. Sci. 39(2): 153-165 (1989) - [j24]Karl R. Abrahamson, Andrew Adler, Rachel Gelbart, Lisa Higham, David G. Kirkpatrick:
The Bit Complexity of Randomized Leader Election on a Ring. SIAM J. Comput. 18(1): 12-29 (1989) - [c16]Binay K. Bhattacharya, David G. Kirkpatrick, Godfried T. Toussaint:
Determining Sector Visibility of a Polygon. Symposium on Computational Geometry 1989: 247-253 - [c15]David G. Kirkpatrick, Stephen K. Wismath:
Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract). WADS 1989: 325-334 - 1988
- [j23]