Abstract
Given a set P of n points in the plane in general position, and a set of non-crossing segments with endpoints in P, we seek to place a new point q such that the constrained Delaunay triangulation of P ∪ {q} has the largest possible minimum angle. The expected running time of our (randomized) algorithm is O(n2 log n) on any input, improving the near-cubic time of the best previously known algorithm. Our algorithm is somewhat complex, and along the way we develop a simpler cubic-time algorithm quite different from the ones already known.
Original language | English (US) |
---|---|
Pages | 395-400 |
Number of pages | 6 |
State | Published - 2014 |
Event | 26th Canadian Conference on Computational Geometry, CCCG 2014 - Halifax, Canada Duration: Aug 11 2014 → Aug 13 2014 |
Other
Other | 26th Canadian Conference on Computational Geometry, CCCG 2014 |
---|---|
Country/Territory | Canada |
City | Halifax |
Period | 8/11/14 → 8/13/14 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics