Name
Abstract | ||
|---|---|---|
A terrain M is the graph of a bivariate function. We assume that M is represented as a triangulated surface with N vertices. A contour (or isoline) of M is a connected component of a level set of M. Generically, each contour is a closed polygonal curve; at "critical" levels these curves may touch each other or collapse to a point. We present I/O efficient algorithms for the following two problems related to computing contours of M: (i) Given a sequence l1 ls of real numbers, we present an I/O-optimal algorithm that reports all contours of M at heights l1 , ... , ls using O(sort(N) + T/B) I/Os, where T is the total number edges in the output contours, B is the "block size," and sort(N) is the number of I/Os needed to sort N elements. The algorithm uses O(N/B) disk blocks. Each contour is generated individually with its composing segments sorted in clockwise or counterclockwise order. Moreover, our algorithm generates information on how the contours are nested. (ii) We can preprocess M, using O(sort(N)) I/Os, into a linear-size data structure so that all contours at a given height can be reported using O(logB N + T/B) I/Os, where T is the output size. Each contour is generated individually with its composing segments sorted in clockwise or counterclockwise order. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1377676.1377698 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
o-efficient efficient algorithm,o-optimal algorithm,n vertex,computing contour,terrain m,o efficient algorithm,n element,logb n,output contour,composing segment,counterclockwise order,connected component,data structure,geographic information system,terrains,level set | Discrete mathematics,Data structure,Combinatorics,Vertex (geometry),sort,Terrain,Level set,Algorithm,Input/output,Connected component,Polygonal chain,Mathematics | Conference |
Citations | PageRank | References |
5 | 0.51 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Lars Arge | 2 | 2066 | 255.14 |
| Thomas Mølhave | 3 | 136 | 11.85 |
| Bardia Sadri | 4 | 72 | 9.70 |