Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection R of input regions known in advance. Building on recent work by Löffler and Snoeyink, we show how to leverage our knowledge of R for faster Delaunay computation. Our approach needs no fancy machinery and optimally handles a wide variety of inputs, e.g., overlapping disks of different sizes and fat regions. Keywords: Delaunay triangulation - Data imprecision - Quadtree.
Buchin, K., Löffler, M., Morin, P., & Mulzer, W. (2011). Preprocessing imprecise points for Delaunay triangulation: Simplified and extended. Algorithmica, 61(3), 674-693. https://doi.org/10.1007/s00453-010-9430-0