default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid 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
2020 – today
- 2024
[j78]William S. Evans
, David G. Kirkpatrick:
Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time. Algorithms 17(6): 246 (2024)- [j77]David G. Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro:
On the power of bounded asynchrony: convergence by autonomous robots with limited visibility. Distributed Comput. 37(3): 279-308 (2024) - 2023
- [j76]Shaun M. Fallat, David G. Kirkpatrick, Hans Ulrich Simon, Abolghasem Soltani, Sandra Zilles:
On Batch Teaching Without Collusion. J. Mach. Learn. Res. 24: 40:1-40:33 (2023) - [c90]William S. Evans, David G. Kirkpatrick:
Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time. FCT 2023: 162-175 - [c89]William S. Evans, David G. Kirkpatrick:
A Frequency-Competitive Query Strategy for Maintaining Low Collision Potential Among Moving Entities. WAOA 2023: 14-28 - 2021
- [c88]David G. Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro:
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. PODC 2021: 9-19 - [i7]David G. Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro:
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. CoRR abs/2105.13042 (2021) - 2020
- [j75]Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, Ján Manuch:
Approximate majority analyses using tri-molecular chemical reaction networks. Nat. Comput. 19(1): 249-270 (2020)
2010 – 2019
- 2019
- [c87]David G. Kirkpatrick, Hans Ulrich Simon, Sandra Zilles:
Optimal Collusion-Free Teaching. ALT 2019: 506-528 - [c86]Daniel Busto, William S. Evans, David G. Kirkpatrick:
Minimizing Interference Potential Among Moving Entities. SODA 2019: 2400-2418 - [i6]David G. Kirkpatrick, Hans Ulrich Simon, Sandra Zilles:
Optimal Collusion-Free Teaching. CoRR abs/1903.04012 (2019) - 2018
- [j74]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
- [j73]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]David G. Kirkpatrick, Paul Liu:
Characterizing minimum-length coordinated motions for two discs. CCCG 2016: 252-259 - [i4]David G. Kirkpatrick, Paul Liu:
Characterizing minimum-length coordinated motions for two discs. CoRR abs/1607.04005 (2016) - 2015
- [j72]David G. Kirkpatrick:
An O(lg lg OPT)-Approximation Algorithm for Multi-guarding Galleries. Discret. Comput. Geom. 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
- [j71]David G. Kirkpatrick, Boting Yang, Sandra Zilles:
A Polynomial-Time Algorithm for Computing the Resilience of Arrangements of Ray Sensors. Int. J. Comput. Geom. Appl. 24(3): 225-236 (2014) - [j70]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
Computational Aspects of M.C. Escher's Ribbon Patterns. Theory Comput. Syst. 54(4): 640-658 (2014) - [j69]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. Electron. Colloquium Comput. Complex. TR14 (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]Daniel Busto, William S. Evans, David G. Kirkpatrick:
On k-Guarding Polygons. CCCG 2013 - [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. SoCG 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
- [j68]David G. Kirkpatrick:
Guest editorʼs foreword. Comput. Geom. 45(5-6): 199 (2012) - [j67]David G. Kirkpatrick:
Guest Editor's Foreword. Discret. Comput. Geom. 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
- [j66]James King, David G. Kirkpatrick:
Improved Approximation for Guarding Simple Galleries from the Perimeter. Discret. Comput. Geom. 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]Kuan-Chieh Robert Tseng, David G. Kirkpatrick:
Input-Thrifty Extrema Testing. ISAAC 2011: 554-563 - [c67]David G. Kirkpatrick, Sandra Zilles:
Competitive Search in Symmetric Trees. WADS 2011: 560-570 - 2010
- [j65]Stephane Durocher, David G. Kirkpatrick, Lata Narayanan:
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Wirel. 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]David G. Kirkpatrick:
Determining the robustness of sensor barriers. CCCG 2010: 227 - [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
- [j64]Stephane Durocher, David G. Kirkpatrick:
The projection median of a set of points. Comput. Geom. 42(5): 364-375 (2009) - [j63]Pavol Hell, David G. Kirkpatrick:
Linear-time certifying algorithms for near-graphical sequences. Discret. Math. 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]David G. Kirkpatrick:
Hyperbolic Dovetailing. ESA 2009: 516-527 - 2008
- [j62]Stephane Durocher, David G. Kirkpatrick:
Bounded-Velocity Approximation of Mobile Euclidean 2-Centres. Int. J. Comput. Geom. 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. SCG 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
- [j61]Sergey Bereg, Prosenjit Bose, David G. Kirkpatrick:
Equitable subdivisions within polygonal regions. Comput. Geom. 34(1): 20-27 (2006) - [j60]Stephane Durocher, David G. Kirkpatrick:
The Steiner Centre of a Set of Points: Stability, Eccentricity, and Applications to Mobile Facility Location. Int. J. Comput. Geom. Appl. 16(4): 345-372 (2006) - [j59]Sergey Bereg, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Competitive Algorithms for Maintaining a Mobile Center. Mob. Networks Appl. 11(2): 177-186 (2006) - [j58]Prosenjit Bose, Luc Devroye, William S. Evans, David G. Kirkpatrick:
On the Spanning Ratio of Gabriel Graphs and beta-Skeletons. SIAM J. Discret. Math. 20(2): 412-427 (2006) - [j57]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]Jonathan Backer, David G. Kirkpatrick:
Bounded-Curvature Path Normalization. CCCG 2006 - [c56]Tetsuo Asano, David G. Kirkpatrick:
Distance Trisector Curves in Regular Convex Distance Me. ISVD 2006: 8-17 - 2005
- [j56]Daniel Archambault, William S. Evans, David G. Kirkpatrick:
Computing the Set of all the Distant Horizons of a Terrain. Int. J. Comput. Geom. 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. SCG 2005: 278-287 - 2004
- [j55]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning. Discret. Comput. Geom. 31(1): 139-171 (2004) - [j54]William S. Evans, David G. Kirkpatrick:
Restructuring ordered binary trees. J. Algorithms 50(2): 168-193 (2004) - [c53]William S. Evans, Daniel 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
- [j53]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) - [j52]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
- [j51]David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann:
Kinetic Collision Detection for Simple Polygons. Int. J. Comput. Geom. Appl. 12(1-2): 3-27 (2002) - [j50]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. SCG 2002: 170-178 - [c45]David G. Kirkpatrick, Bettina Speckmann:
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. SCG 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]Sergei Bespamyatnikh, David G. Kirkpatrick:
Constrained Equitable 3-Cuttings. JCDCG 2002: 72-83 - [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
- [j49]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
- [j48]Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. Discret. Comput. Geom. 24(4): 605-622 (2000) - [c40]David G. Kirkpatrick:
Guarding Alcove-Free Galleries . CCCG 2000 - [c39]David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann:
Kinetic collision detection for simple polygons. SCG 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]William S. Evans, David G. Kirkpatrick:
Restructuring ordered binary trees. SODA 2000: 477-486
1990 – 1999
- 1999
- [j47]David G. Kirkpatrick, Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time. Int. J. Comput. Geom. Appl. 9(1): 53-62 (1999) - [c34]Sergei Bespamyatnikh, David G. Kirkpatrick:
Rectilinear 2-center problems. CCCG 1999 - [c33]Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. SCG 1999: 49-58 - 1998
- [j46]Heinz Breu, David G. Kirkpatrick:
Unit disk graph recognition is NP-hard. Comput. Geom. 9(1-2): 3-24 (1998) - [j45]David G. Kirkpatrick, Madhukar K. Reddy, C. Pandu Rangan, Anand Srinivasan:
Partial and Perfect Path Covers of Cographs. Discret. Appl. Math. 89(1-3): 143-153 (1998) - 1997
- [j44]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
- [j43]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel Construction of Binary Trees with Near Optimal Weighted Path Lengt. Algorithmica 15(2): 172-192 (1996) - [j42]David G. Kirkpatrick, Stephen K. Wismath:
Determining Bar-representability for Ordered Weighted Graphs. Comput. Geom. 6: 99-122 (1996) - [j41]Pavol Hell, David G. Kirkpatrick, Brenda Li:
Rounding in Symmetric Matrices and Undirected Graphs. Discret. Appl. Math. 70(1): 1-21 (1996) - [j40]Michael McAllister, David G. Kirkpatrick, Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. Discret. Comput. Geom. 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). SCG 1996: 252-263 - 1995
- [j39]David G. Kirkpatrick, Jack Snoeyink:
Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation. Fundam. Informaticae 22(4): 353-370 (1995) - [j38]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. GD 1995: 88-98 - [c28]David G. Kirkpatrick, Jack Snoeyink:
Computing Common Tangents Without a Separating Line. WADS 1995: 183-193 - 1994
- [j37]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
- [j36]David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri:
Computing the Intersection-Depth of Polyhedra. Algorithmica 9(6): 518-533 (1993) - [j35]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) - [j34]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. SCG 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
- [j33]David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap:
Quantitative Steinitz's Theorems Applications to Multifingered Grasping. Discret. Comput. Geom. 7: 295-318 (1992) - [j32]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O (n log log n) Time with Simple Data Structures. Discret. Comput. Geom. 7: 329-346 (1992) - 1991
- [c24]