Publications with Matt Dickerson
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.
On triangulating three-dimensional polygons.
G. Barequet, M. Dickerson, and D. Eppstein.
12th ACM Symp. Comp. Geom., Philadelphia, 1996, pp. 38–47.
Comp. Geom. Theory & Applications 10: 155–170, 1998.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.
Confluent drawings: visualizing non-planar diagrams in a planar way.
M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
arXiv:cs.CG/0212046.
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.
Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation.
M. Dickerson, D. Eppstein, and K. Wortman.
arXiv:0812.0607.
7th Int. Symp. Voronoi Diagrams in Science and Engineering (ISVD 2010), Quebec City, Canada, pp. 13–22.Investigates Voronoi diagrams for a "smoothed distance" in which the distance between two points p and q is inversely weighted by the perimeter of triangle opq for a fixed point o, its relation to dilation of star networks centered at o, and its generalization to minimization diagrams of certain convex functions. When the function to be minimized is suitably well-behaved, its level sets form pseudocircles, the bisectors of the minimization diagram form pseudoline arrangements, and the diagram itself has linear complexity.
Animating a continuous family of two-site distance function Voronoi diagrams (and a proof of a complexity bound on the number of non-empty regions).
M. Dickerson and D. Eppstein.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, video and multimedia track, pp. 92–93.We investigate distance from a pair of sites defined as the sum of the distances to each site minus a parameter times the distance between the two sites. A given set of n sites defines n(n-1)/2 pairs and n(n-1)/2 distances in this way, from which we can determine a Voronoi diagram. As we show, for a wide range of parameters, the diagram has relatively few regions because the pairs that have nonempty Voronoi regions must be Delaunay edges.
Cloning Voronoi diagrams via retroactive data structures.
M. Dickerson, D. Eppstein, and M. T. Goodrich.
arXiv:1006.1921.
18th Eur. Symp. Algorithms, Liverpool, 2010.
Springer, Lecture Notes in Comp. Sci. 6346, 2010, pp. 362–373.We analyze the security of an online geometric database that allows planar nearest-neighbor queries but that does not wish the entire database to be copied by a competitor. We show that, under several models of how the query answers are returned, the database can be copied in a linear or near-linear number of queries. Our method for the competitor to copy the database is based on simulating Fortune's sweep-line algorithm for Voronoi diagrams, backtracking when the simulation discovers the existence of another point that invalidates earlier parts of the Voronoi diagram construction, and using retroactive data structures to perform the backtracking steps efficiently.
On 2-site Voronoi diagrams under geometric distance functions.
G. Barequet, M. Dickerson, D. Eppstein, D. Hodorkovsky, and K. Vyatkina.
27th Eur. Worksh. Comp. Geom., Antoniushaus Morschach, Switzerland, 2011, pp. 59–62.
Proc. 8th Int. Symp. Voronoi Diagrams in Science and Engineering, Qing Dao, China, 2011, pp. 31–38.
arXiv:1105.4130.
J. Computer Science and Technology 28 (2): 267–277, 2013.We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.