Name
Abstract | ||
|---|---|---|
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(\frac{N}{B}{\rm log}_{M/B}\frac{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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11561071_33 | ESA |
Keywords | Field | DocType |
o-efficient construction,delaunay triangulations,triangulating n point,extensive set,rm log,constraining segment,o-efficient algorithm,disk block size,algorithm degrades,memory size,constrained delaunay triangulation | Block size,Discrete mathematics,Combinatorics,Expectation–maximization algorithm,Computational geometry,Input/output,Voronoi diagram,Mathematics,Hilbert curve,Delaunay triangulation,Auxiliary memory | Conference |
Volume | ISSN | ISBN |
3669 | 0302-9743 | 3-540-29118-0 |
Citations | PageRank | References |
15 | 1.03 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Lars Arge | 2 | 2066 | 255.14 |
| Ke Yi | 3 | 1659 | 77.79 |