David G. Kirkpatrick

David G. Kirkpatrick's AcademicInfluence.com Rankings

Computer Science

#1358

World Rank

#1405

Historical Rank

Machine Learning

#2473

World Rank

#2505

Historical Rank

Artificial Intelligence

#2758

World Rank

#2801

Historical Rank

Database

#4099

World Rank

#4262

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is David G. Kirkpatrick Influential?

(Suggest an Edit or Addition)

According to Wikipedia, David Galer Kirkpatrick is a Professor Emeritus of computer science at the University of British Columbia. He is known for the Kirkpatrick–Seidel algorithm and his work on polygon triangulation, and for co-inventing α-shapes and the β-skeleton. He received his PhD from the University of Toronto in 1974.

(See a Problem?)

David G. Kirkpatrick's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

On the shape of a set of points in the plane (1983) (1584)
Optimal Search in Planar Subdivisions (1983) (755)
The Ultimate Planar Convex Hull Algorithm? (1986) (408)
Unit disk graph recognition is NP-hard (1998) (325)
A Framework for Computational Morphology (1985) (310)
Linear Time Euclidean Distance Algorithms (1995) (308)
Efficient computation of continuous skeletons (1979) (282)
A Simple Parallel Tree Contraction Algorithm (1989) (249)
Determining the Separation of Preprocessed Polyhedra - A Unified Approach (1990) (248)
A Linear Algorithm for Determining the Separation of Convex Polyhedra (1985) (244)
Quantitative Steinitz's theorems with applications to multifingered grasping (1990) (219)
Fast Detection of Polyhedral Intersection (1983) (214)
On the Complexity of General Graph Factor Problems (1981) (177)
On the completeness of a generalized matching problem (1978) (161)
Right-Triangulated Irregular Networks (2001) (156)
On the Spanning Ratio of Gabriel Graphs and beta-skeletons (2002) (151)
Kinetic collision detection for simple polygons (2000) (125)
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks (2008) (116)
Computing the intersection-depth of polyhedra (1993) (115)
A time-space tradeoff for sorting on non-oblivious machines (1979) (99)
Upper Bounds for Sorting Integers on Random Access Machines (1981) (98)
Dynamic Voronoi diagrams (1983) (79)
A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem (1980) (73)
Generalizing Ham Sandwich Cuts to Equitable Subdivisions (1999) (72)
A Note on Delaunay and Optimal Triangulations (1980) (69)
Fast Detection of Polyhedral Intersections (1982) (67)
Output-size sensitive algorithms for finding maximal vectors (1985) (67)
Algorithmic aspects of constrained unit disk graphs (1996) (65)
A compact piecewise-linear voronoi diagram for convex sites in the plane (1993) (65)
The geometry of beam tracing (1985) (60)
Improved Approximation for Guarding Simple Galleries from the Perimeter (2010) (59)
Packings by cliques and by finite families of graphs (1984) (55)
Polygon triangulation in O(n log log n) time with simple data-structures (1990) (50)
Addition Requirements for Matrix and Transposed Matrix Products (1988) (50)
A simple existence criterion for (g (1990) (49)
ON THE SPANNING RATIO OF GABRIEL GRAPHS AND β-SKELETONS (2002) (46)
Mobile facility location (2000) (44)
Parallel processing for efficient subdivision search (1987) (43)
Absolute and arbitrary orientation of single-molecule shapes (2018) (43)
Curvature-bounded traversals of narrow corridors (2005) (43)
Approximating Barrier Resilience in Wireless Sensor Networks (2009) (43)
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces (2003) (43)
Tight degree bounds for pseudo-triangulations of points (2003) (41)
A Unified Lower Bound for Selection and Set Partitioning Problems (1981) (41)
Parallel Construction of Subdivision Hierarchies (1989) (41)
Polygonal Intersection Searching (1982) (40)
Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation (1995) (40)
On Restricted Two-Factors (1988) (40)
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons (2002) (37)
Mobile facility location (extended abstract) (2000) (35)
The Projection Median of a Set of Points in R2 (2009) (32)
On the Complexity of Recognizing Intersection and Touching Graphs of Disks (1995) (28)
Computing Common Tangents Without a Separating Line (1995) (28)
Right Triangular Irregular Networks (1997) (28)
Algorithms for Degree Constrained Graph Factors of Minimum Deficiency (1993) (28)
Efficient algorithms for centers and medians in interval and circular‐arc graphs (2002) (27)
Generalizing Ham Sandwich Cuts to Equitable Subdivisions (2000) (27)
Probabilistic solitude verification on a ring (1986) (27)
Topics in the complexity of combinatorial algorithms. (1974) (25)
Finding curvature-constrained paths that avoid polygonal obstacles (2007) (25)
The Steiner Centre of a Set of Points: Stability, Eccentricity, and Applications to Mobile Facility Location (2006) (24)
Implicitly Searching Convolutions and Computing Depth of Collision (1990) (24)
Some Graph-Colouring Theorems with Applications to Generalized Connection Networks (1985) (23)
Determining graph properties from matrix representations (1974) (23)
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability (2014) (23)
The Bit Complexity of Randomized Leader Election on a Ring (1989) (22)
Rectilinear 2-center problems (1999) (22)
On Generalized Matching Problems (1981) (22)
On Barrier Resilience of Sensor Networks (2011) (22)
Pseudo approximation algorithms, with applications to optimal motion planning (2002) (22)
Alphabetic Minimax Trees (1985) (21)
Hyperbolic Dovetailing (2009) (20)
Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems (2013) (18)
Equitable subdivisions within polygonal regions (2006) (17)
Restructuring ordered binary trees (2000) (16)
Swapping Colored Tokens on Graphs (2015) (16)
d1-optimal motion for a rod (extended abstract) (1996) (16)
Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract) (1989) (15)
Competitive Algorithms for Maintaining a Mobile Center (2006) (15)
Determining sector visibility of a polygon (1989) (15)
Finding Nearest Larger Neighbors (2009) (15)
On the additions necessary to compute certain functions (1972) (14)
Bounded-Velocity Approximation of Mobile Euclidean 2-Centres (2008) (14)
A time-space tradeoff for sorting and related non-oblivious computations (1979) (14)
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths (2008) (14)
Linear-time certifying algorithms for near-graphical sequences (2009) (14)
Bar-representable visibility graphs and a related network flow problem (1989) (13)
Parallel construction of near optimal binary trees (1990) (13)
Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilience (2014) (13)
On pseudosimilarity in trees (1983) (12)
Polygon triangulation inO(n log logn) time with simple data structures (1992) (12)
Tentative prune-and-search for computing Voronoi vertices (1993) (11)
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning (2004) (11)
Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning (2011) (11)
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ (2004) (11)
Optimal Collusion-Free Teaching (2019) (11)
Parallel recognition of complement reducible graphs and cotree construction (1990) (10)
Separation Sensitive Kinetic Separation Structures for Convex Polygons (2000) (10)
Establishing order in planar subdivisions (1987) (10)
An $$O(\lg \lg {\mathrm {OPT}})$$O(lglgOPT)-Approximation Algorithm for Multi-guarding Galleries (2015) (10)
Approximating Shortest Paths in Arrangements of Lines (1996) (10)
Competitive query strategies for minimising the ply of the potential locations of moving points (2013) (10)
Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain (1996) (10)
Competitive Algorithms for Mobile Centers ∗ (9)
Distance Trisector Curves in Regular Convex Distance Me (2006) (9)
Input-Thrifty Extrema Testing (2011) (9)
Computing the set of all distant horizons of a terrain (2004) (8)
An optimal parallel minimax tree algorithm (1990) (8)
Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs (2000) (8)
Characterizing minimum-length coordinated motions for two discs (2016) (8)
Tight lower bounds for probabilistic solitude verification on anonymous rings (1994) (8)
Simplifying Analyses of Chemical Reaction Networks for Approximate Majority (2017) (7)
Discrete Dubins Paths (2012) (7)
A Polynomial-Time Algorithm for Computing the Resilience of Arrangements of Ray Sensors (2014) (6)
Randomized distributed computing on rings (1988) (6)
Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors (2012) (6)
Optimal Parallel Algorithms for Convex Polygon Separation (1989) (5)
Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50 (2013) (5)
An O ( lg lg OPT ) -Approximation Algorithm for Multi-guarding Galleries (2015) (5)
Adequate Requirements for Rational Functions (1975) (5)
Factors and Flows (1986) (5)
Minimizing Co-location Potential of Moving Entities (2016) (5)
A Parallel Tree Contraction Algorithm (1987) (5)
Minimizing the trace length of a rod endpoint in the presence of polygonal obstacles is NP-hard (2003) (4)
Probabilistic Leader Election on Rings of Known Size (1991) (4)
Determining Bar-representability for Ordered Weighted Graphs (1996) (4)
A note onf-factors in directed and undirected multigraphs (1986) (4)
Constrained Equitable 3-Cuttings (2002) (4)
Parallel algorithms for fractional and maximal independent sets in planar graphs (1990) (4)
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility (2021) (4)
Minimizing Interference Potential Among Moving Entities (2019) (4)
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem (2014) (4)
Preference-based Teaching of Unions of Geometric Objects (2017) (4)
Rounding in Symmetric Matrices and Undirected Graphs (1996) (4)
Probabilistic Solitude Detection II: Ring Size Known Exactly (1987) (3)
Partial and Perfect Path Covers of Cographs (1998) (3)
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time (1999) (3)
Query Strategies for Minimizing the Ply of the Potential Locations of Entities Moving with Different Speeds (2014) (3)
Lower bounds on average-case delay for video-on-demand broadcast protocols (2007) (3)
Finding extrema with unary predicates (1990) (3)
Competitive Search in Symmetric Trees (2011) (3)
On k-Guarding Polygons (2013) (3)
Lower and Upper Bounds for Tracking Mobile Users (2002) (3)
On the hardness of turn-angle-restricted rectilinear cycle cover problems (2002) (3)
Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings (1997) (3)
Parallel construction of binary trees with near optimal weighted path length (1996) (3)
Foundations for multifile design by application partitioning (1982) (2)
The Gaussian Centre of a Set of Mobile Points (2003) (2)
On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case (2013) (2)
Finding Nearest Larger Neighbors A Case Study in Algorithm Design and Analysis (2009) (2)
An exact algebraic predicate for maintaining the topology of the voronoi diagram for circles (2002) (2)
A Parallel Algorithm for Finding Maximal Independent Sets in Planar Graphs (1987) (2)
Probabilistic Evaluation of Common Functions On Rings of Known Size (1988) (2)
Bounded-Curvature Path Normalization (2006) (2)
Randomized function evaluation on a ring (1987) (2)
Progressive Alignment of Shapes (2016) (2)
Efficient Construction of Binary Trees with Almost Optimal Weighted Path Length (1989) (2)
The gaussian centre and the projection centre of a set of points in r3 (2004) (2)
Computational aspects of escher tilings (2002) (1)
Computational Aspects of M.C. Escher’s Ribbon Patterns (2014) (1)
Probabilistic Solitude Detection I: Ring Size Known Approximately (1987) (1)
Leven and M. Sharir. Planning a Purely Translational Motion for a Convex Object in Two- Dimensional Space Using Generalized Voronoi Diagrams (1998) (1)
Optimal Algorithms for Probalistic Solitude Detection On Anomymous Rings (1990) (1)
(g,f) - Factors \& Packings, When g>f: Characterizations \& Algorithms (1983) (1)
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns (2012) (1)
Guarding Galleries with No Nooks (extended Abstract) (2000) (1)
Minimizing the endpoint trace length of rod motions amidst polygonal obstacles is NP-hard (2003) (1)
Determining the robustness of sensor barriers (2010) (0)
Additional Requirements for Matrix \& Transposed Matrix Products (1986) (0)
Marriage Before Conquest: A Variation on the Divide \& Conquer Paradigm (1983) (0)
Õ ( √ n )-Space and Polymomial-time Algorithm for the Planar Directed Graph Reachability Problem (2014) (0)
Guest Editor’s Foreword (2012) (0)
Multi-guard covers for polygonal regions (2010) (0)
Minimizing the trace length of a rod endpoint amidst polygonal obstacles is NP-hard (2003) (0)
On the Shape o f a Set o f Points in the Plane (0)
Probabilistic Solitude Detection on Rings of Known Size (1986) (0)
Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals (2017) (0)
Randomized Function on a Ring (Preliminary Version) (1987) (0)
Tentative Prune- and- Search Fixed-Points with Applications to Geometric Computation (1993) (0)
Can Nearest Neighbor Searching Be Simple and Always Fast? (2011) (0)
4.3 a Data Structuring Approach (1994) (0)
Computational Aspects of M.C. Escher’s Ribbon Patterns (2013) (0)
Proving Newtonian Arbiters Correct , Almost Surely (2009) (0)
Guarding Alcove-Free Galleries (2000) (0)
Forest embeddings in regular graphs of large girth (1981) (0)
A Simple Optimal Parallel List Ranking Algorithm (1987) (0)
4. Conclusion 5. Acknowledgment 3. the Width in Three Dimensions 2. the Width in Two Dimensions Computing the Width of a Set (1988) (0)
AN APPROXIMATION ALGORITHM FOR GENERAL MINIMUM-LENGTH BOUNDED-CURVATURE PATHS (2007) (0)

This paper list is powered by the following services:

Other Resources About David G. Kirkpatrick

en.wikipedia.org

What Schools Are Affiliated With David G. Kirkpatrick?

David G. Kirkpatrick is affiliated with the following schools:

David G. Kirkpatrick's Academic­Influence.com Rankings

Why Is David G. Kirkpatrick Influential?

David G. Kirkpatrick's Published Works

Published Works

Other Resources About David G. Kirkpatrick

What Schools Are Affiliated With David G. Kirkpatrick?

Image Attributions

David G. Kirkpatrick's AcademicInfluence.com Rankings