# Publications

AuthorTitleJournal/Proceedings
David L. Millman,
Steven Love
Timothy M. Chan
Jack Snoeyink
Computing the Nearest Neighbor Transform Exactly with Only Double Precision ISVD '12: Proceedings of the 9th annual symposium on Voronoi Diagrams
Abstract: The nearest neighbor transform of a binary image assigns to each pixel the index of the nearest black pixel -- it is the discrete analog of the Voronoi diagram. Implementations that compute the transform use numerical calculations to perform geometric tests, so they may produce erroneous results if the calculations require more arithmetic precision than is available. Liotta, Preparata, and Tamassia, in 1999, suggested designing algorithms that not only minimize time and space resources, but also arithmetic precision.
A simple algorithm using double precision can compute the nearest neighbor transform: compare the squared distances of each pixel to all black pixels, but this is inefficient when many pixels are black. We develop and implement efficient algorithms, computing the nearest neighbor transform of an image in linear time with respect to the number of pixels, while still using only double precision.
BibTeX:
@inproceedings{mv11_cccg,
author = {David L. Millman and Steven Love and Timothy M. Chan and Jack Snoeyink},
title = {Computing the Nearest Neighbor Transform Exactly with Only Double Precision},
booktitle = {ISVD '12: Proceedings of the 9th annual symposium on
Voronoi Diagrams},
year = {2012},
pages = {66--74},
publisher = {IEEE}
}
David L. Millman,
Vishal Verma
A Slow Algorithm for Computing the Gabriel Graph with Double Precision CCCG '11: Proceedings of the twenty-third Canadian Conference on Computational Geometry
Abstract: When designing algorithms, time and space usage are commonly considered. In 1999, Liotta, Preparata and Tamassia proposed that we could also analyze the precision of an algorithm. We present our first steps towards the goal of efficiently computing the Gabriel graph of a finite set of sites, while restricting ourselves to only double precision.
BibTeX:
@inproceedings{mv11_cccg,
author = {David L. Millman and Vishal Verma},
title = {A Slow Algorithm for Computing the Gabriel Graph with Double Precision},
booktitle = {CCCG '11: Proceedings of the 23rd Canadian Conference on
Computational geometry},
year = {2011},
url = {http://2011.cccg.ca/PDFschedule/papers/paper87.pdf}
}
David L. Millman,
Jack Snoeyink
Computing Planar Voronoi Diagrams in Double Precision: An Example of Degree-driven Algorithm Design SCG '10: Proceedings of the twenty-sixth annual Symposium on Computational Geometry 2010
Abstract: Geometric algorithms use numerical computations to perform geometric tests, so correct algorithms may produce erroneous results if insufficient arithmetic precision is available. Liotta, Preparata, and Tamassia, in 1999, suggested that algorithm design, which traditional considers running time and memory space, could also consider precision as a resource. They demonstrated that a Voronoi diagram of sites on a $U\times U$ grid could be rounded to answer "Post Office" queries on the same grid with only double precision, even though computing a Voronoi diagram requires the quadruple-precision InCircle test. We develop a similar rounded "Voronoi diagram" that can be computed directly using only double precision by randomized incremental construction in $O(n \log n\log U)$ expected time and $O(n)$ expected space. The structure produced can answer Post Office queries, which ask for the nearest site to a query on the grid, even though it doesn't even use sufficient precision to determine a Delaunay triangulation.
BibTeX:
@inproceedings{ms10_scg,
author = {David L. Millman and Jack Snoeyink},
title = {Computing planar Voronoi diagrams in double precision: a further example of
degree-driven algorithm design},
booktitle = {SCG '10: Proceedings of the 26th annual symposium on
Computational geometry},
year = {2010},
isbn = {978-1-4503-0016-2},
pages = {386--392},
location = {Snowbird, Utah, USA},
doi = {http://doi.acm.org/10.1145/1810959.1811024},
publisher = {ACM},
address = {New York, NY, USA},
}
Timothy M. Chan,
David L. Millman,
Jack Snoeyink
Discrete Voronoi Diagrams and Post Office Query Structures without the InCircle Predicate Proceedings of the Nineteenth Annual Fall Workshop on Computational Geometry 2009
Abstract: We develop an algorithm to compute the Voronoi diagram (or distance transform) of $n$ sites (feature pixels) in a $U \times U$ grid using double precision, instead of the usualy 4-fold precision for the InCircle test. Our algorithm runs in $O(U^2 + n \log U )$ time.
BibTeX:
@inproceedings{cms09_fwcg,
Author = {Timothy M. Chan and David L. Millman and Jack Snoeyink},
Booktitle = {Proceedings of the Nineteenth Annual Fall Workshop on
Computational Geometry},
Pages = {33--34},
Title = {Discrete {V}oronoi Diagrams and Post Office Query Structures
without the InCircle Predicate},
Year = {2009}
}
David L. Millman,
Jack Snoeyink
Computing the Reduced Voronoi Diagram in Triple Precision Proceedings of the Algorithms and Data Structure Symposium (WADS) 2009
Abstract: In a paper that considered arithmetic precision as a limited resource in the design and analysis of algorithms, Liotta, Preparata and Tamassia deﬁned an “implicit Voronoi diagram” supporting logarithmic-time proximity queries using predicates of twice the precision of the input and query coordinates. They reported, however, that computing this diagram uses five times the input precision. We define a reduced-precision Voronoi diagram that similarly supports proximity queries, and describe a randomized incremental construction using only three times the input precision. The expected construction time is O(n(log n + log \mu)), where \mu is the length of the longest Voronoi edge; we can construct the implicit Voronoi from the reduced-precision Voronoi in linear time.
BibTeX:
Author = {David L. Millman and Jack Snoeyink},
Title = {Computing the Implicit {V}oronoi Diagram in Triple Precision},
Booktitle = {Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings},
Pages = {495-506},
Publisher = {Springer},
Series = {Lecture Notes in Computer Science},
Volume = {5664},
Year = {2009}
}
David L. Millman,
Jack Snoeyink
Degree-driven algorithm design for computing the Voronoi diagram Proceedings of the Eighteenth Annual Fall Workshop on Computational Geometry 2008
Abstract: The Voronoi diagram is the classic proximity query structure. It finds the nearest point from a finite set S to a given query point q and it is the partition of the plane into the maximal connected regions. The Voronoi diagram’s topological structure can be computed using four times the precision of the input, but representing its vertices requires five times the input precision. Furthermore, using the Voronoi diagram to solve proximity queries in O(log n) requires six times the precision of the input and query points. Liotta, Preparata, and Tamassia [3] have derived a structure from the Voronoi diagram whose computation requires five times the precision of the input, but which supports proximity queries in O(log n) time, using only two times the input precision. In this paper, we show how this structure can be computed directly, using at most triple precision in O(n(log n + log g)) time where g is the bisector length.
BibTeX:
@inproceedings{ms08,
Author = {David L. Millman and Jack Snoeyink},
Booktitle = {Proceedings of the Eighteenth Annual Fall Workshop on Computational Geometry},
Pages = {20--21},
Title = {Degree-driven algorithm design for computing the Voronoi diagram},
Year = {2008}
}
Andrea Mantler,
Jack Snoeyink
Intersecting Red and Blue Line Segments in Optimal Time and Precision JCDCG '00: Revised Papers from the Japanese Conference on Discrete and Computational Geometry
Abstract: A common geometric problem in computer graphics and geographic information systems is to compute the arrangement of a set of n segments that can be colored red and blue so that there are no red/red or blue/blue crossings. We give a sweep algorithm that uses the minimum arithmetic precision and runs in optimal O(n log n + k) time and O(n) space to output an arrangement with k vertices, or O(n log n) time to determine k. Our initial implementation in Java can be found at http://www.cs.unc.edu/~snoeyink/demos/rbseg.
BibTeX:
@inproceedings{ms01,
Author = {Andrea Mantler and Jack Snoeyink},
Booktitle = {JCDCG '00: Revised Papers from the Japanese Conference on
Discrete and Computational Geometry},
Pages = {244--251},
Title = {Intersecting Red and Blue Line Segments in Optimal Time and Precision},
Year = {2001}
}

# Presentations

TitleLocation(s)
Degree-Driven Geometric Algorithm Design for Computing Volumes of CSG Models Young Researchers Forum at CG Week, June 2012, UNC
Abstract: We describe a framework for computing volumes of CSG models. The framework was designed using Liotta, Preparata, and Tamassia's degree-driven algorithm design paradigm, which suggests that the algorithm designer balances minimizing the time, space, and precision used by an algorithm. The framework serves as an example of how degree-driven algorithm design can be used in practice to produce a fast and accurate implementation.
Voronoi Diagrams and Problem Transformations UNC's sixth annual Department of Computer Science Undergraduate Research Symposium, April 2012
Abstract: We illustrate the power of transforming one problem into another, specifically in creating a Voronoi diagram, through solving the nearest-neighbor problem. We are able to meet restrictions on time, space, and arithmetic precision by transforming the nearest-neighbor problem into computing a series of discrete upper envelopes. Our algorithm is faster than the de facto standard algorithm used by MATLAB, and we can guarantee correctness, because we only rely on two degrees of arithmetic precision. Voronoi diagrams have applications in path planning, database queries, wireless network distribution, art and more. Due to the transformable nature of the Voronoi diagram, our algorithm has implications for other similar geometric problems like Delaunay triangulation.
Degree-Driven Geometric Algorithm Design Graduating Bits Session at Innovations in Theoretical Computer Science, 2012
Abstract:
Two examples of degree-driven algorithm design The Institute of Science and Technology (IST) Austria, December 2009
Duke Algorithms Seminar, February 2010
Abstract: Geometric algorithms are often designed for RealRAM, a computational model that provides arbitrary precision arithmetic operations at unit cost. Commodity hardware provides finite precision, and the resulting arithmetic errors can violate geometric axioms. For example, the intersection of two lines may produce coordinates that do not actually test as lying on either line. Thus, provably correct algorithms can fail on commodity hardware. RealRAM can be simulated with additional computational costs. Liotta, Preparata and Tamassia proposed that in addition to considering the resources of time and space, an algorithm designer could also consider the precision necessary to guarantee a correct implementation. They called this design technique degree-driven algorithm design.

I will describe two applications of this design technique for computing "Post Office" query structures. Standard techniques use four-fold precision to compute the query structure, and six-fold precision to execute queries. I will describe a triple and a double precision algorithm that builds data structure supporting logarithmic time queries with only double precision.

# Posters

TitleLocation(s)
Degree-driven algorithm design for computing the Voronoi diagram Fall Workshop on Computational Geometry, Albany NY, 2008
Abstract: The Voronoi diagram is the classic proximity query structure. It finds the nearest point from a finite set S to a given query point q and it is the partition of the plane into the maximal connected regions. The Voronoi diagram’s topological structure can be computed using four times the precision of the input, but representing its vertices requires five times the input precision. Furthermore, using the Voronoi diagram to solve proximity queries in O(log n) requires six times the precision of the input and query points. Liotta, Preparata, and Tamassia [3] have derived a structure from the Voronoi diagram whose computation requires five times the precision of the input, but which supports proximity queries in O(log n) time, using only two times the input precision. In this paper, we show how this structure can be computed directly, using at most triple precision in O(n(log n + log g)) time where g is the bisector length.
Lower Degree Predicates for the Additively Weighted Voronoi Diagram MAA Mathfest, Madison WI, 2008
Abstract: This work considers the problem of incrementally constructing additively weighted Voronoi diagrams in 2d. Incremental constructions assume a diagram of k sites and considers the insertion of a new site s. In general, this type of construction consist of two steps: first, identify the the conflict region, the set of diagram components which s destroys; second, repair the conflict region as to return the diagram to a valid state. In the paper Dynamic Additively Weighted Voronoi Diagrams in 2d, Karavelas and Yvinec describe such a procedure, determining the conflict region using predicates of algebraic degree 14. We propose a different set of predicates for determining this region, which achieves the same result, but has an algebraic degree of only 6. In addition, this method handles degeneracies in a manner which results in a diagram insensitive to insertion order. Finally, we show that implementing these lower degree predicates result in 39 to 66 percent less running time.

# Research Flyers

Title
Degree-driven Geometric Algorithm Design