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, eg, overlapping disks of different sizes and fat regions.
|Title of host publication||Algorithms and Data Structures (Proceedings 11th International Workshop, WADS 2009, Banff, Alberta, Canada, August 21-23, 2009)|
|Editors||F. Dehne, M. Gavrilova, J.-R. Sack, C.D. Tóth|
|Place of Publication||Berlin|
|Publication status||Published - 2009|
|Name||Lecture Notes in Computer Science|