Arrow Research search

Author name cluster

David G. Kirkpatrick

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

FOCS Conference 1993 Conference Paper

A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane

  • Michael McAllister
  • David G. Kirkpatrick
  • Jack Snoeyink

In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using O(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices, we compute this diagram optimally in O(klog n) deterministic time for the Euclidean metric and in O(klog nlog m) deterministic time for the convex distance function defined by a convex m-gon. >

Details

FOCS Conference 1979 Conference Paper

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines

  • Allan Borodin
  • Michael J. Fischer
  • David G. Kirkpatrick
  • Nancy A. Lynch
  • Martin Tompa

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

Details

FOCS Conference 1979 Conference Paper

Efficient Computation of Continuous Skeletons

  • David G. Kirkpatrick

An O(n lgn) algorithm is presented for the construction of skeletons of arbitrary n-line polygonal figures. This algorithm is based on an O(n lgn) algorithm for the construction of generalized Voronoi diagrams (our generalization replaces point sets by sets of line segments constrained to intersect only at end points). The generalized Voronoi diagram algorithm employs a linear time algorithm for the merging of two arbitrary (standard) Voronoi diagrams.

Details