David G. Kirkpatrick

ORCID

Publication Activity (10 Years)

Years Active: 1972-2024
Publications (10 Years): 20

Top Venues

Publications

William S. Evans, David G. Kirkpatrick
Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time. Algorithms 17 (6) (2024)
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) (2024)
Shaun M. Fallat, David G. Kirkpatrick, Hans Ulrich Simon, Abolghasem Soltani, Sandra Zilles
On Batch Teaching Without Collusion. J. Mach. Learn. Res. 24 (2023)
William S. Evans, David G. Kirkpatrick
Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time. FCT (2023)
William S. Evans, David G. Kirkpatrick
A Frequency-Competitive Query Strategy for Maintaining Low Collision Potential Among Moving Entities. WAOA (2023)
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)
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 (2021)
Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, Ján Manuch
Approximate majority analyses using tri-molecular chemical reaction networks. Nat. Comput. 19 (1) (2020)
David G. Kirkpatrick, Hans Ulrich Simon, Sandra Zilles
Optimal Collusion-Free Teaching. ALT (2019)
David G. Kirkpatrick, Hans Ulrich Simon, Sandra Zilles
Optimal Collusion-Free Teaching. CoRR (2019)
Daniel Busto, William S. Evans, David G. Kirkpatrick
Minimizing Interference Potential Among Moving Entities. SODA (2019)
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 (2018)
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
Swapping Colored Tokens on Graphs. CoRR (2018)
Toshiki Saitoh, David G. Kirkpatrick
Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals. WALCOM (2017)
Ziyuan Gao, David G. Kirkpatrick, Christoph Ries, Hans Ulrich Simon, Sandra Zilles
Preference-based Teaching of Unions of Geometric Objects. ALT (2017)
Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, Ján Manuch
Simplifying Analyses of Chemical Reaction Networks for Approximate Majority. DNA (2017)
Ashwin Gopinath, David G. Kirkpatrick, Paul W. K. Rothemund, Chris Thachuk
Progressive Alignment of Shapes. CCCG (2016)
David G. Kirkpatrick, Paul Liu
Characterizing minimum-length coordinated motions for two discs. CCCG (2016)
David G. Kirkpatrick, Paul Liu
Characterizing minimum-length coordinated motions for two discs. CoRR (2016)
William S. Evans, David G. Kirkpatrick, Maarten Löffler, Frank Staals
Minimizing Co-location Potential of Moving Entities. SIAM J. Comput. 45 (5) (2016)
David G. Kirkpatrick
An O(lg lg OPT)-Approximation Algorithm for Multi-guarding Galleries. Discret. Comput. Geom. 53 (2) (2015)
Katsuhisa Yamanaka, Takashi Horiyama, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
Swapping Colored Tokens on Graphs. WADS (2015)
Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. MFCS (2) (2014)
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 (2014)
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. 21 (2014)
Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger
Computational Aspects of M.C. Escher's Ribbon Patterns. Theory Comput. Syst. 54 (4) (2014)
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) (2014)
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)
Daniel Busto, William S. Evans, David G. Kirkpatrick
On k-Guarding Polygons. CCCG (2013)
David G. Kirkpatrick
Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50. Space-Efficient Data Structures, Streams, and Algorithms (2013)
Tetsuo Asano, David G. Kirkpatrick
Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems. WADS (2013)
Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk
On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case. JCDCGG (2013)
David G. Kirkpatrick
Guest Editor's Foreword. Discret. Comput. Geom. 47 (4) (2012)
Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns. FUN (2012)
Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk
Discrete Dubins Paths CoRR (2012)
David G. Kirkpatrick
Guest editorʼs foreword. Comput. Geom. 45 (5-6) (2012)
David Yu Cheng Chan, David G. Kirkpatrick
Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors. ALGOSENSORS (2012)
Kuan-Chieh Robert Tseng, David G. Kirkpatrick
Input-Thrifty Extrema Testing. ISAAC (2011)
Victor Alvarez, David G. Kirkpatrick, Raimund Seidel
Can Nearest Neighbor Searching Be Simple and Always Fast? ESA (2011)
Kuan-Chieh Robert Tseng, David G. Kirkpatrick
On Barrier Resilience of Sensor Networks. ALGOSENSORS (2011)
David G. Kirkpatrick, Irina Kostitsyna, Valentin Polishchuk
Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning. CCCG (2011)
James King, David G. Kirkpatrick
Improved Approximation for Guarding Simple Galleries from the Perimeter. Discret. Comput. Geom. 46 (2) (2011)
David G. Kirkpatrick, Sandra Zilles
Competitive Search in Symmetric Trees. WADS (2011)
Zohreh Jabbari, William S. Evans, David G. Kirkpatrick
Multi-guard covers for polygonal regions. CCCG (2010)
David G. Kirkpatrick
Determining the robustness of sensor barriers. CCCG (2010)
James King, David G. Kirkpatrick
Improved Approximation for Guarding Simple Galleries from the Perimeter CoRR (2010)
Stephane Durocher, David G. Kirkpatrick, Lata Narayanan
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Wirel. Networks 16 (1) (2010)
David G. Kirkpatrick
Hyperbolic Dovetailing. ESA (2009)
Sergey Bereg, David G. Kirkpatrick
Approximating Barrier Resilience in Wireless Sensor Networks. ALGOSENSORS (2009)
Stephane Durocher, David G. Kirkpatrick
The projection median of a set of points. Comput. Geom. 42 (5) (2009)
Pavol Hell, David G. Kirkpatrick
Linear-time certifying algorithms for near-graphical sequences. Discret. Math. 309 (18) (2009)
Tetsuo Asano, Sergey Bereg, David G. Kirkpatrick
Finding Nearest Larger Neighbors. Efficient Algorithms (2009)
Jonathan Backer, David G. Kirkpatrick
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths. ISAAC (2008)
Stephane Durocher, David G. Kirkpatrick, Lata Narayanan
On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks. ICDCN (2008)
Stephane Durocher, David G. Kirkpatrick
Bounded-Velocity Approximation of Mobile Euclidean 2-Centres. Int. J. Comput. Geom. Appl. 18 (3) (2008)
Jonathan Backer, David G. Kirkpatrick
Finding curvature-constrained paths that avoid polygonal obstacles. SCG (2007)
Wei-Lung Dustin Tseng, David G. Kirkpatrick
Lower bounds on average-case delay for video-on-demand broadcast protocols. SODA (2007)
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) (2006)
Jonathan Backer, David G. Kirkpatrick
Bounded-Curvature Path Normalization. CCCG (2006)
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) (2006)
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) (2006)
Tetsuo Asano, David G. Kirkpatrick
Distance Trisector Curves in Regular Convex Distance Me. ISVD (2006)
Sergey Bereg, Prosenjit Bose, David G. Kirkpatrick
Equitable subdivisions within polygonal regions. Comput. Geom. 34 (1) (2006)
Sergey Bereg, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal
Competitive Algorithms for Maintaining a Mobile Center. Mob. Networks Appl. 11 (2) (2006)
Sergey Bereg, David G. Kirkpatrick
Curvature-bounded traversals of narrow corridors. SCG (2005)
Stephane Durocher, David G. Kirkpatrick
. CCCG (2005)
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) (2005)
William S. Evans, Daniel Archambault, David G. Kirkpatrick
Computing the set of all distant horizons of a terrain. CCCG (2004)
Stephane Durocher, David G. Kirkpatrick
. CCCG (2004)
William S. Evans, David G. Kirkpatrick
Restructuring ordered binary trees. J. Algorithms 50 (2) (2004)
Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning. Discret. Comput. Geom. 31 (1) (2004)
William S. Evans, David G. Kirkpatrick
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. SODA (2004)
Prosenjit Bose, David G. Kirkpatrick, Zaiqing Li
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Comput. Geom. 26 (3) (2003)
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) (2003)
Stephane Durocher, David G. Kirkpatrick
The Gaussian Centre of a Set of Mobile Points. CCCG (2003)
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)
David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann
Kinetic Collision Detection for Simple Polygons. Int. J. Comput. Geom. Appl. 12 (1-2) (2002)
Sergei Bespamyatnikh, David G. Kirkpatrick
Constrained Equitable 3-Cuttings. JCDCG (2002)
Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap
Pseudo approximation algorithms, with applications to optimal motion planning. SCG (2002)
Stephane Durocher, David G. Kirkpatrick
On the hardness of turn-angle-restricted rectilinear cycle cover problems. CCCG (2002)
Sergei Bespamyatnikh, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal
Lower and Upper Bounds for Tracking Mobile Users. IFIP TCS (2002)
Prosenjit Bose, Luc Devroye, William S. Evans, David G. Kirkpatrick
On the Spanning Ratio of Gabriel Graphs and beta-skeletons. LATIN (2002)
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) (2002)
David G. Kirkpatrick, Bettina Speckmann
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. SCG (2002)
Francois Anton, David G. Kirkpatrick, Darka Mioc
An exact algebraic predicate for maintaining the topology of the voronoi diagram for circles. CCCG (2002)
Lutz Kettner, David G. Kirkpatrick, Bettina Speckmann
Tight degree bounds for pseudo-triangulations of points. CCCG (2001)
William S. Evans, David G. Kirkpatrick, G. Townsend
Right-Triangulated Irregular Networks. Algorithmica 30 (2) (2001)
David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann
Kinetic collision detection for simple polygons. SCG (2000)
David G. Kirkpatrick, Bettina Speckmann
Separation Sensitive Kinetic Separation Structures for Convex Polygons. JCDCG (2000)
Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. Discret. Comput. Geom. 24 (4) (2000)
David G. Kirkpatrick
Guarding Alcove-Free Galleries . CCCG (2000)
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)
Sergei Bespamyatnikh, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal
Mobile facility location. DIAL-M (2000)
William S. Evans, David G. Kirkpatrick
Restructuring ordered binary trees. SODA (2000)
David G. Kirkpatrick, Jack Snoeyink
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time. Int. J. Comput. Geom. Appl. 9 (1) (1999)
Sergei Bespamyatnikh, David G. Kirkpatrick
Rectilinear 2-center problems. CCCG (1999)
Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. SCG (1999)
Heinz Breu, David G. Kirkpatrick
Unit disk graph recognition is NP-hard. Comput. Geom. 9 (1-2) (1998)
David G. Kirkpatrick, Madhukar K. Reddy, C. Pandu Rangan, Anand Srinivasan
Partial and Perfect Path Covers of Cographs. Discret. Appl. Math. 89 (1-3) (1998)
Lisa Higham, David G. Kirkpatrick, Karl R. Abrahamson, Andrew Adler
Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings. J. Algorithms 23 (2) (1997)

David G. Kirkpatrick.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

David G. Kirkpatrick