Math @ Duke

Publications [#235473] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Yi, K, I/Oefficient construction of constrained delaunay triangulations,
Lecture notes in computer science, vol. 3669
(2005),
pp. 355366, ISSN 03029743
(last updated on 2018/07/22)
Abstract: In this paper, we designed and implemented an I/Oefficient algorithm for constructing constrained Delaunay triangulations. If the number of constraining segments is smaller than the memory size, our algorithm runs in expected O(N/B logM/B N/B) I/Os for triangulating N points in the plane, where M is the memory size and B is the disk block size. If there are more constraining segments, the theoretical bound does not hold, but in practice the performance of our algorithm degrades gracefully. Through an extensive set of experiments with both synthetic and real data, we show that our algorithm is significantly faster than existing implementations. © SpringerVerlag Berlin Heidelberg 2005.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

