**Iterated nearest neighbors and finding minimal polytopes**.

D. Eppstein and J. Erickson.

Tech. Rep. 92-71, ICS, UCI, 1992.

*4th ACM-SIAM Symp. Discrete Algorithms,*Austin, 1993, pp. 64–73.

*Disc. Comp. Geom.*11: 321–350, 1994.Showed that for various optimization criteria, the optimal polygon containing

*k*of*n*points must be near one of the points, hence one can transform time bounds involving several factors of*n*to bounds linear in*n*but polynomial in*k.*Used as a subroutine are data structures for finding several nearest neighbors in rectilinear metric spaces, and algorithms for finding the deepest point in an arrangement of cubes or spheres.(BibTeX – Citations – Jeff's pub list entry – CiteSeer)

**Dynamic Euclidean minimum spanning trees and extrema of binary functions**.

D. Eppstein.

Tech. Rep. 92-05, ICS, UCI, 1992.

Tech. Rep. 92-88, ICS, UCI, 1992.

*Disc. Comp. Geom.*13: 111–122, 1995.Shows that bichromatic nearest neighbors can be maintained under point insertion and deletion essentially as quickly as known solutions to the post office problem, and that the minimum spanning tree can be maintained in the same time except for an additive O(sqrt

*n*) needed for solving the corresponding graph problem. TR 92-88's title was actually "Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions". TR 92-05's title left out the part about maxima; that version gave a slower algorithm superseded by the result in 92-88.(BibTeX – Citations – Closest pair project page – CiteSeer)

**Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees**.

P.K. Agarwal, D. Eppstein, and J. Matoušek.

*33rd IEEE Symp. Foundations of Comp. Sci.,*Pittsburgh, 1992, pp. 80–89.This conference paper merged my results from "Dynamic Euclidean minimum spanning trees" with results of my co-authors on nearest neighbors and halfspace range searching.

**Algorithms for proximity problems in higher dimensions**.

M. T. Dickerson and D. Eppstein.

*Comp. Geom. Theory & Applications*5: 277–291, 1996.Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the

*k*nearest neighbors to each point in a given point set.(BibTeX – Full paper – Citations – CiteSeer – ACM DL)

**Parallel construction of quadtrees and quality triangulations**.

M. Bern, D. Eppstein, and S.-H. Teng.

*3rd Worksh. Algorithms and Data Structures,*Montreal, 1993.

Springer,*Lecture Notes in Comp. Sci.*709, 1993, pp. 188–199.

Tech. Rep. 614, MIT Lab. for Comp. Sci., 1994.

*Int. J. Comp. Geom. & Appl.*9 (6): 517–532, 1999.A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.

(BibTeX – CiteSeer – Citations – ACM DL)

**The diameter of nearest neighbor graphs**.

D. Eppstein.

Tech. Rep. 92-76, ICS, UCI, 1992.Any connected nearest neighbor forest with diameter

*D*has O(*D*^{6}) vertices. This was later further improved to O(*D*^{5}) and merged with results of Paterson and Yao into "On nearest neighbor graphs".(BibTeX – Citations – CiteSeer)

**On nearest-neighbor graphs**.

D. Eppstein, M. S. Paterson, and F. F. Yao.

*Disc. Comp. Geom.*17: 263–282, 1997.Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter

*D*has O(*D*^{9}) vertices. This paper is the journal version; my contribution consists of improving that bound to O(*D*^{5}), which is tight.(BibTeX – CiteSeer – Citations)

**Algorithms for stable matching and clustering in a grid**.

D. Eppstein, M. T. Goodrich, and N. Mamano.

arXiv:1704.02303

*Proc. 18th International Workshop on Combinatorial Image Analysis (IWCIA 2017)*, Plovdiv, Bulgaria, 2017.

Springer,*Lecture Notes in Comp. Sci.*10256 (2017), pp. 117–131.Motivated by redistricting, we consider geometric variants of the stable matching problem in which points (such as the pixels of a discretization of the unit square) are to be matched to a smaller number of centers such that each center has the same number of matches and no match is unstable with respect to Euclidean distances. We show how to solve such problems in polylogarithmic time per matched point, experiment with practical heuristics for solving these problems, and test methods for moving the centers to improve the shape of the matched regions.

**Defining equitable geographic districts in road networks via stable matching**.

D. Eppstein, M. T. Goodrich, D. Korkmaz, and N. Mamano.

arXiv:1706.09593

*Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)*, Redondo Beach, California, to appear.

We cluster road networks (modeled as planar graphs, or more generally as graphs obeying a separator theorem) with a given set of cluster centers, by matching graph vertices to centers stably according to distance: no unmatched vertex and center should have smaller distances than the matched pairs for the same points. We provide a separator-based data structure for dynamic nearest neighbor queries in planar or separated graphs, which allows the optimal stable clustering to be constructed in time

*O*(*n*^{3/2}log*n*). We also experiment with heuristics for fast practical construction of this clustering.**Reactive proximity data structures for graphs**.

D. Eppstein, M. T. Goodrich, and N. Mamano.

arXiv:1803.04555.

*Proc. 13th Latin American Theoretical Informatics Symposium (LATIN 2018)*, Buenos Aires, Argentina.

Springer,*Lecture Notes in Comp. Sci.*10807 (2018), pp. 777–789.We develop data structures for solving nearest neighbor queries for dynamic subsets of vertices in a planar graph, or more generally for a graph in any graph class with small separators (polynomial expansion).

**Stable-matching Voronoi diagrams: combinatorial complexity and algorithms**.

G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.

arXiv:1804.09411

*Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)*, Prague, to appear.The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.

Geometry – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.