Loading...
Please wait, while we are loading the content...
Similar Documents
I/O-Efficient Algorithms for Computing Contours on a Terrain
| Content Provider | Semantic Scholar |
|---|---|
| Author | Agarwal, Pankaj K. Arge, Lars Mølhave, Thomas Sadri, Bardia |
| Copyright Year | 2008 |
| 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/Oecient algorithms for the following two problems related to computing contours of M: (i) Given a sequence ‘1 < < ‘s of real numbers, we present an I/O-optimal algorithm that reports all contours of M at heights ‘1;:::;‘s 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://users.cs.duke.edu/~thomasm/papers/agarwalSoCG08.pdf |
| Alternate Webpage(s) | https://users.cs.duke.edu/~pankaj/publications/papers/contour-dem.pdf |
| Alternate Webpage(s) | http://www.cs.au.dk/~thomasm/papers/agarwalSoCG08.pdf |
| Alternate Webpage(s) | https://www.cs.duke.edu/~pankaj/publications/papers/contour-dem.pdf |
| Alternate Webpage(s) | https://users.cs.duke.edu/~thomasm/papers/agarwal_socg08.pdf |
| Alternate Webpage(s) | http://biogeometry.duke.edu/pubs-pankaj/papers/contour-dem.pdf |
| Alternate Webpage(s) | http://www.cs.duke.edu/~pankaj/publications/papers/contour-dem.pdf |
| Alternate Webpage(s) | http://www.daimi.au.dk/~thomasm/papers/agarwalSoCG08.pdf |
| Alternate Webpage(s) | https://www.cs.duke.edu/~thomasm/papers/agarwal_socg08.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
