Abstract
We describe a randomized algorithm that, given a set of points in the plane, computes the best location to insert a new point, such that the Delaunay triangulation of the resulting point set has the largest possible minimum angle. The expected running time of our algorithm is at most cubic on any input, improving the roughly quartic time of the best previously known algorithm.
Original language | English (US) |
---|---|
Pages | 259-263 |
Number of pages | 5 |
State | Published - 2013 |
Event | 25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada Duration: Aug 8 2013 → Aug 10 2013 |
Other
Other | 25th Canadian Conference on Computational Geometry, CCCG 2013 |
---|---|
Country/Territory | Canada |
City | Waterloo |
Period | 8/8/13 → 8/10/13 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics