Publications
| Author | Title | Journal/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 defined 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: @inproceedings{ms09_wads, 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} } |
||