| 2008 |
|---|
| 115 | EE | Stephane Durocher,
David G. Kirkpatrick,
Lata Narayanan:
On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks.
ICDCN 2008: 546-557 |
| 114 | EE | Jonathan Backer,
David G. Kirkpatrick:
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths.
ISAAC 2008: 628-643 |
| 113 | EE | Stephane Durocher,
David G. Kirkpatrick:
Bounded-Velocity Approximation of Mobile Euclidean 2-Centres.
Int. J. Comput. Geometry Appl. 18(3): 161-183 (2008) |
| 2007 |
|---|
| 112 | EE | Wei-Lung Dustin Tseng,
David G. Kirkpatrick:
Lower bounds on average-case delay for video-on-demand broadcast protocols.
SODA 2007: 834-842 |
| 111 | EE | Jonathan Backer,
David G. Kirkpatrick:
Finding curvature-constrained paths that avoid polygonal obstacles.
Symposium on Computational Geometry 2007: 66-73 |
| 2006 |
|---|
| 110 | EE | Jonathan Backer,
David G. Kirkpatrick:
Bounded-Curvature Path Normalization.
CCCG 2006 |
| 109 | EE | William S. Evans,
David G. Kirkpatrick:
Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ.
ACM Transactions on Algorithms 2(4): 661-678 (2006) |
| 108 | EE | 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) |
| 107 | EE | Sergey Bereg,
Binay K. Bhattacharya,
David G. Kirkpatrick,
Michael Segal:
Competitive Algorithms for Maintaining a Mobile Center.
MONET 11(2): 177-186 (2006) |
| 106 | EE | 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) |
| 2005 |
|---|
| 105 | EE | Stephane Durocher,
David G. Kirkpatrick:
The Projection Median of a Set of Points in R2.
CCCG 2005: 47-51 |
| 104 | EE | Sergey Bereg,
David G. Kirkpatrick:
Curvature-bounded traversals of narrow corridors.
Symposium on Computational Geometry 2005: 278-287 |
| 103 | EE | Daniel 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) |
| 2004 |
|---|
| 102 | EE | Stephane Durocher,
David G. Kirkpatrick:
The gaussian centre and the projection centre of a set of points in r3.
CCCG 2004: 140-144 |
| 101 | EE | William S. Evans,
Daniel Archambault,
David G. Kirkpatrick:
Computing the set of all distant horizons of a terrain.
CCCG 2004: 76-79 |
| 100 | EE | 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 |
| 99 | EE | 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) |
| 98 | EE | William S. Evans,
David G. Kirkpatrick:
Restructuring ordered binary trees.
J. Algorithms 50(2): 168-193 (2004) |
| 2003 |
|---|
| 97 | | 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 |
| 96 | | Stephane Durocher,
David G. Kirkpatrick:
The Gaussian Centre of a Set of Mobile Points.
CCCG 2003: 123-127 |
| 95 | | 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) |
| 94 | EE | 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) |
| 2002 |
|---|
| 93 | EE | Stephane Durocher,
David G. Kirkpatrick:
On the hardness of turn-angle-restricted rectilinear cycle cover problems.
CCCG 2002: 13-16 |
| 92 | EE | 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 |
| 91 | | Sergei Bespamyatnikh,
Binay K. Bhattacharya,
David G. Kirkpatrick,
Michael Segal:
Lower and Upper Bounds for Tracking Mobile Users.
IFIP TCS 2002: 47-58 |
| 90 | EE | Sergei Bespamyatnikh,
David G. Kirkpatrick:
Constrained Equitable 3-Cuttings.
JCDCG 2002: 72-83 |
| 89 | EE | Prosenjit Bose,
Luc Devroye,
William S. Evans,
David G. Kirkpatrick:
On the Spanning Ratio of Gabriel Graphs and beta-skeletons.
LATIN 2002: 479-493 |
| 88 | EE | Tetsuo Asano,
David G. Kirkpatrick,
Chee-Keng Yap:
Pseudo approximation algorithms, with applications to optimal motion planning.
Symposium on Computational Geometry 2002: 170-178 |
| 87 | EE | David G. Kirkpatrick,
Bettina Speckmann:
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons.
Symposium on Computational Geometry 2002: 179-188 |
| 86 | | David G. Kirkpatrick,
Jack Snoeyink,
Bettina Speckmann:
Kinetic Collision Detection for Simple Polygons.
Int. J. Comput. Geometry Appl. 12(1-2): 3-27 (2002) |
| 2001 |
|---|
| 85 | EE | Lutz Kettner,
David G. Kirkpatrick,
Bettina Speckmann:
Tight degree bounds for pseudo-triangulations of points.
CCCG 2001: 117-120 |
| 84 | EE | William S. Evans,
David G. Kirkpatrick,
G. Townsend:
Right-Triangulated Irregular Networks.
Algorithmica 30(2): 264-286 (2001) |
| 2000 |
|---|
| 83 | EE | David G. Kirkpatrick:
Guarding Alcove-Free Galleries .
CCCG 2000 |
| 82 | EE | Sergei Bespamyatnikh,
Binay K. Bhattacharya,
David G. Kirkpatrick,
Michael Segal:
Mobile facility location.
DIAL-M 2000: 46-53 |
| 81 | | 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 |
| 80 | EE | David G. Kirkpatrick,
Bettina Speckmann:
Separation Sensitive Kinetic Separation Structures for Convex Polygons.
JCDCG 2000: 222-236 |
| 79 | EE | William S. Evans,
David G. Kirkpatrick:
Restructuring ordered binary trees.
SODA 2000: 477-486 |
| 78 | EE | David G. Kirkpatrick,
Jack Snoeyink,
Bettina Speckmann:
Kinetic collision detection for simple polygons.
Symposium on Computational Geometry 2000: 322-330 |
| 77 | EE | Sergei Bespamyatnikh,
David G. Kirkpatrick,
Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions.
Discrete & Computational Geometry 24(4): 605-622 (2000) |
| 1999 |
|---|
| 76 | EE | Sergei Bespamyatnikh,
David G. Kirkpatrick:
Rectilinear 2-center problems.
CCCG 1999 |
| 75 | EE | Sergei Bespamyatnikh,
David G. Kirkpatrick,
Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions.
Symposium on Computational Geometry 1999: 49-58 |
| 74 | | David G. Kirkpatrick,
Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time.
Int. J. Comput. Geometry Appl. 9(1): 53- (1999) |
| 1998 |
|---|
| 73 | | Heinz Breu,
David G. Kirkpatrick:
Unit disk graph recognition is NP-hard.
Comput. Geom. 9(1-2): 3-24 (1998) |
| 72 | EE | 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 |
|---|
| 71 | | 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 |
|---|
| 70 | | Prosenjit Bose,
William S. Evans,
David G. Kirkpatrick,
Michael McAllister,
Jack Snoeyink:
Approximating Shortest Paths in Arrangements of Lines.
CCCG 1996: 143-148 |
| 69 | | Prosenjit Bose,
David G. Kirkpatrick,
Zaiqing Li:
Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain.
CCCG 1996: 217-222 |
| 68 | EE | Tetsuo Asano,
David G. Kirkpatrick,
Chee-Keng Yap:
d1-Optimal Motion for a Rod (Extended Abstract).
Symposium on Computational Geometry 1996: 252-263 |
| 67 | | David G. Kirkpatrick,
Teresa M. Przytycka:
Parallel Construction of Binary Trees with Near Optimal Weighted Path Lengt.
Algorithmica 15(2): 172-192 (1996) |
| 66 | | David G. Kirkpatrick,
Stephen K. Wismath:
Determining Bar-representability for Ordered Weighted Graphs.
Comput. Geom. 6: 99-122 (1996) |
| 65 | EE | 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) |
| 64 | EE | Pavol Hell,
David G. Kirkpatrick,
Brenda Li:
Rounding in Symmetric Matrices and Undirected Graphs.
Discrete Applied Mathematics 70(1): 1-21 (1996) |
| 1995 |
|---|
| 63 | | Heinz Breu,
David G. Kirkpatrick:
On the Complexity of Recognizing Intersection and Touching Graphs of Disks.
Graph Drawing 1995: 88-98 |
| 62 | | David G. Kirkpatrick,
Jack Snoeyink:
Computing Common Tangents Without a Separating Line.
WADS 1995: 183-193 |
| 61 | | 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) |
| 60 | EE | 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) |
| 1994 |
|---|
| 59 | EE | 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 |
|---|
| 58 | | David G. Kirkpatrick,
Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time.
CCCG 1993: 163-168 |
| 57 | | Michael McAllister,
David G. Kirkpatrick,
Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane
FOCS 1993: 573-582 |
| 56 | EE | David G. Kirkpatrick,
Jack Snoeyink:
Tentative Prune-and-Search for Computing Voronoi Vertices.
Symposium on Computational Geometry 1993: 133-142 |
| 55 | | David P. Dobkin,
John Hershberger,
David G. Kirkpatrick,
Subhash Suri:
Computing the Intersection-Depth of Polyhedra.
Algorithmica 9(6): 518-533 (1993) |
| 54 | | 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) |
| 53 | | Pavol Hell,
David G. Kirkpatrick:
Algorithms for Degree Constrained Graph Factors of Minimum Deficiency.
J. Algorithms 14(1): 115-138 (1993) |
| 1992 |
|---|
| 52 | | David G. Kirkpatrick,
Bhubaneswar Mishra,
Chee-Keng Yap:
Quantitative Steinitz's Theorems Applications to Multifingered Grasping.
Discrete & Computational Geometry 7: 295-318 (1992) |
| 51 | | 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 |
|---|
| 50 | | Karl R. Abrahamson,
Andrew Adler,
Lisa Higham,
David G. Kirkpatrick:
Probabilistic Leader Election on Rings of Known Size.
WADS 1991: 481-495 |
| 1990 |
|---|
| 49 | | David P. Dobkin,
David G. Kirkpatrick:
Determining the Separation of Preprocessed Polyhedra - A Unified Approach.
ICALP 1990: 400-413 |
| 48 | | David G. Kirkpatrick,
Feng Gao:
Finding Extrema with Unary Predicates.
SIGAL International Symposium on Algorithms 1990: 156-164 |
| 47 | | 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 |
| 46 | EE | David G. Kirkpatrick,
Teresa M. Przytycka:
Parallel Construction of near Optimal binary Trees.
SPAA 1990: 234-243 |
| 45 | EE | David G. Kirkpatrick,
Teresa M. Przytycka:
An optimal parallel minimax tree algorithm.
SPDP 1990: 293-300 |
| 44 | | David G. Kirkpatrick,
Bhubaneswar Mishra,
Chee-Keng Yap:
Quantitative Steinitz's Theorems with Applications to Multifingered Grasping
STOC 1990: 341-351 |
| 43 | EE | 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 |
| 42 | EE | N. Dadoun,
David G. Kirkpatrick:
Parallel algorithms for fractional and maximal independent sets in planar graphs.
Discrete Applied Mathematics 27(1-2): 69-83 (1990) |
| 41 | EE | David G. Kirkpatrick,
Teresa M. Przytycka:
Parallel recognition of complement reducible graphs and cotree construction.
Discrete Applied Mathematics 29(1): 79-96 (1990) |
| 40 | EE | Katherine Heinrich,
Pavol Hell,
David G. Kirkpatrick,
Guizhen Liu:
A simple existence criterion for (g<f)- factors.
Discrete Mathematics 85(3): 313-317 (1990) |
| 1989 |
|---|
| 39 | EE | Binay K. Bhattacharya,
David G. Kirkpatrick,
Godfried T. Toussaint:
Determining Sector Visibility of a Polygon.
Symposium on Computational Geometry 1989: 247-253 |
| 38 | | David G. Kirkpatrick,
Stephen K. Wismath:
Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract).
WADS 1989: 325-334 |
| 37 | | Karl R. Abrahamson,
Andrew Adler,
Lisa Higham,
David G. Kirkpatrick:
Randomized Function Evaluation on a Ring.
Distributed Computing 3(3): 107-117 (1989) |
| 36 | | Karl R. Abrahamson,
N. Dadoun,
David G. Kirkpatrick,
Teresa M. Przytycka:
A Simple Parallel Tree Contraction Algorithm.
J. Algorithms 10(2): 287-302 (1989) |
| 35 | | N. Dadoun,
David G. Kirkpatrick:
Parallel Construction of Subdivision Hierarchies.
J. Comput. Syst. Sci. 39(2): 153-165 (1989) |
| 34 | | 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) |
| 1988 |
|---|
| 33 | | David G. Kirkpatrick:
Establishing Order in Planar Subdivisions.
Discrete & Computational Geometry 3: 267-280 (1988) |
| 32 | | Michael Kaminski,
David G. Kirkpatrick,
Nader H. Bshouty:
Addition Requirements for Matrix and Transposed Matrix Products.
J. Algorithms 9(3): 354-364 (1988) |
| 31 | | Pavol Hell,
David G. Kirkpatrick,
Jan Kratochvíl,
Igor Kríz:
On Restricted Two-Factors.
SIAM J. Discrete Math. 1(4): 472-484 (1988) |
| 1987 |
|---|
| 30 | EE | N. Dadoun,
David G. Kirkpatrick:
Parallel Processing for Efficient Subdivision Search.
Symposium on Computational Geometry 1987: 205-214 |
| 29 | EE | David G. Kirkpatrick:
Establishing Order in Planar Subdivisions.
Symposium on Computational Geometry 1987: 316-321 |
| 28 | | Karl R. Abrahamson,
Andrew Adler,
Lisa Higham,
David G. Kirkpatrick:
Randomized Function on a Ring (Preliminary Version).
WDAG 1987: 324-331 |
| 1986 |
|---|
| 27 | | Karl R. Abrahamson,
Andrew Adler,
Lisa Higham,
David G. Kirkpatrick:
Probabilistic Solitude Verification on a Ring.
PODC 1986: 161-173 |
| 26 | | David G. Kirkpatrick,
Raimund Seidel:
The Ultimate Planar Convex Hull Algorithm?
SIAM J. Comput. 15(1): 287-299 (1986) |
| 1985 |
|---|
| 25 | | David P. Dobkin,
David G. Kirkpatrick:
A Linear Algorithm for Determining the Separation of Convex Polyhedra.
J. Algorithms 6(3): 381-392 (1985) |
| 24 | | David G. Kirkpatrick,
Maria M. Klawe:
Alphabetic Minimax Trees.
SIAM J. Comput. 14(3): 514-526 (1985) |
| 1984 |
|---|
| 23 | EE | Pavol Hell,
David G. Kirkpatrick:
Packings by cliques and by finite families of graphs.
Discrete Mathematics 49(1): 45-59 (1984) |
| 22 | | David G. Kirkpatrick,
Stefan Reisch:
Upper Bounds for Sorting Integers on Random Access Machines.
Theor. Comput. Sci. 28: 263-276 (1984) |
| 1983 |
|---|
| 21 | | Herbert Edelsbrunner,
David G. Kirkpatrick,
Raimund Seidel:
On the shape of a set of points in the plane.
IEEE Transactions on Information Theory 29(4): 551-558 (1983) |
| 20 | | I. G. Gowda,
David G. Kirkpatrick,
D. T. Lee,
Amnon Naamad:
Dynamic Voronoi diagrams.
IEEE Transactions on Information Theory 29(5): 724-730 (1983) |
| 19 | EE | David G. Kirkpatrick,
Maria M. Klawe,
Derek G. Corneil:
On pseudosimilarity in trees.
J. Comb. Theory, Ser. B 34(3): 323-339 (1983) |
| 18 | | David G. Kirkpatrick:
Optimal Search in Planar Subdivisions.
SIAM J. Comput. 12(1): 28-35 (1983) |
| 17 | | David G. Kirkpatrick,
Pavol Hell:
On the Complexity of General Graph Factor Problems.
SIAM J. Comput. 12(3): 601-609 (1983) |
| 16 | | David P. Dobkin,
David G. Kirkpatrick:
Fast Detection of Polyhedral Intersection.
Theor. Comput. Sci. 27: 241-253 (1983) |
| 1982 |
|---|
| 15 | | David P. Dobkin,
David G. Kirkpatrick:
Fast Detection of Polyhedral Intersections.
ICALP 1982: 154-165 |
| 14 | EE | Doron Rotem,
Frank Wm. Tompa,
David G. Kirkpatrick:
Foundations for Multifile Design by Application Partitioning.
PODS 1982: 262-267 |
| 13 | | Herbert Edelsbrunner,
Hermann A. Maurer,
David G. Kirkpatrick:
Polygonal Intersection Searching.
Inf. Process. Lett. 14(2): 74-79 (1982) |
| 1981 |
|---|
| 12 | | Pavol Hell,
David G. Kirkpatrick:
On Generalized Matching Problems.
Inf. Process. Lett. 12(1): 33-35 (1981) |
| 11 | EE | David G. Kirkpatrick:
A Unified Lower Bound for Selection and Set Partitioning Problems.
J. ACM 28(1): 150-165 (1981) |
| 10 | EE | David G. Kirkpatrick,
Derek G. Corneil:
Forest embeddings in regular graphs of large girth.
J. Comb. Theory, Ser. B 30(1): 45-60 (1981) |
| 9 | | Allan Borodin,
Michael J. Fischer,
David G. Kirkpatrick,
Nancy A. Lynch,
Martin Tompa:
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.
J. Comput. Syst. Sci. 22(3): 351-364 (1981) |
| 1980 |
|---|
| 8 | | David G. Kirkpatrick:
A Note on Delaunay and Optimal Triangulations.
Inf. Process. Lett. 10(3): 127-128 (1980) |
| 7 | | Derek G. Corneil,
David G. Kirkpatrick:
A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem.
SIAM J. Comput. 9(2): 281-297 (1980) |
| 1979 |
|---|
| 6 | | David G. Kirkpatrick:
Efficient Computation of Continuous Skeletons
FOCS 1979: 18-27 |
| 5 | | Allan Borodin,
Michael J. Fischer,
David G. Kirkpatrick,
Nancy A. Lynch,
Martin Tompa:
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines
FOCS 1979: 319-327 |
| 1978 |
|---|
| 4 | | David G. Kirkpatrick,
Pavol Hell:
On the Completeness of a Generalized Matching Problem
STOC 1978: 240-245 |
| 1977 |
|---|
| 3 | | David G. Kirkpatrick,
Zvi M. Kedem:
Adequate Requirements for Rational Functions.
SIAM J. Comput. 6(1): 188-199 (1977) |
| 1974 |
|---|
| 2 | | David G. Kirkpatrick:
Determining Graph Properties from Matrix Representations
STOC 1974: 84-90 |
| 1972 |
|---|
| 1 | | David G. Kirkpatrick:
On the Additions Necessary to Compute Certain Functions
STOC 1972: 94-101 |
