Finds multiple short paths connecting two terminals in a graph (allowing repeated vertices and edges in the paths) in constant time per path after a preprocessing stage dominated by a single-source shortest path computation. Applications include dynamic programs for the knapsack problem, biological sequence alignment, and maximum inscribed polygons.
(BibTeX -- Full paper -- Citations -- Graehl implementation -- Jiménez-Marzal implementations -- Shibuya implementation -- Martins implementation -- CiteSeer: TR '94, SJC '98 -- ACM DL)
Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.
(BibTeX -- Citations -- CiteSeer -- MIT hypertext bibliography)
It is NP-complete, given a simple polygon in 3-space, to find a triangulated simply-connected surface (without extra vertices) spanning that polygon. If extra vertices are allowed, or the surface may be curved, such a surface exists if and only if the polygon is unknotted; the complexity of testing knottedness remains open. Snoeyink has shown that exponentially many extra vertices may be required for a triangulated spanning disk.
(BibTeX -- SCG paper -- Full paper -- Citations -- CiteSeer -- ACM DL)
We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points.
(Tech. report version -- BibTeX -- Citations -- CiteSeer -- ACM DL)
This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.
(Source code and experimental data -- BibTeX -- SODA paper -- Citations -- CiteSeer -- ACM DL -- JEA home page)
We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the "straight skeleton" of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.
(Jeff's publications page and copy of the journal version -- BibTeX -- Citations -- CiteSeer)
We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.
(Springer abstract -- BibTeX -- CiteSeer -- Citations -- ACM DL -- GDEA)
We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.
(preprint at Erik's web site -- BibTeX -- CiteSeer)
We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n1/4 polylog n) per combinatorial change to the tree for planar graphs.
(BibTeX -- FOCS '98 talk slides -- Citations -- CiteSeer -- ACM DL)
We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(nc) per update for any c > 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.
(BibTeX -- Citations -- SODA talk slides -- ACM DL)
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.
(BibTeX -- Citations -- CiteSeer)
Years -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.