Aarhus University Seal / Aarhus Universitets segl

Lars Arge

I/O-Efficient Construction of Constrained Delaunay Triangulations

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Pankaj Kumar Agarwal, United States
  • Lars Arge
  • Ke Yi, Hong Kong
  • Department of Computer Science

In this paper, we designed and implemented an I/O-efficient 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 NB ) 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.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2005 : 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
EditorsGerth Stølting Brodal, Leonardi Stefano
Number of pages11
PublisherSpringer
Publication year2005
Pages355-366
ISBN (print)978-3-540-29118-3
DOIs
Publication statusPublished - 2005
EventAnnual European Symposium on Algorithms. ESA '05 - Mallorca, Spain
Duration: 3 Oct 20056 Oct 2005
Conference number: 13

Conference

ConferenceAnnual European Symposium on Algorithms. ESA '05
Nummer13
LandSpain
ByMallorca
Periode03/10/200506/10/2005
SeriesLecture Notes in Computer Science
Volume3669

See relations at Aarhus University Citationformats

ID: 10650479