dc.contributor.author | Agarwal, Pankaj K. | |
dc.contributor.author | Arge, Lars | |
dc.contributor.author | Murali, T. M. | |
dc.contributor.author | Kasturi R., Varadarajan | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-18T18:11:44Z | |
dc.date.available | 2011-03-18T18:11:44Z | |
dc.date.issued | 1998 | |
dc.identifier.citation | P. K. Agarwal, L. Arge, T. M. Murali, K. R. Varadarajan, and J. S. Vitter. “I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking,” Proceedings of the 9th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’98), San Francisco, CA, January 1998, 117–126. | |
dc.identifier.uri | http://hdl.handle.net/1808/7190 | |
dc.description.abstract | For a polyhedral terrain C, the contour at z-coordinate h, denoted Ch, is defined to be the intersection of the plane z = h with C. In this paper, we study the contour-line extraction problem, where we want to preprocess C into a data structure so that given a query z-coordinate h, we can report Ch quickly. This is a central problem that arises in geographic information systems (GIS), where terrains are often stored as Triangular Irregular Networks (TINS). We present an I/O-optimal algorithm for this problem which stores a terrain C with N vertices using O(N/B) blocks, where B is the size of a disk block, so that for any query h, the contour ch can be computed using o(log, N + I&l/B) I/O operations, where l&l denotes the size of Ch.
We also present en improved algorithm for a more general problem of blocking bounded-degree planar graphs such as TINS (i.e., storing them on disk so that any graph traversal algorithm can traverse the graph in an I/O-efficient manner), and apply it to two problms that arise in GIS. | |
dc.language.iso | en_US | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dc.relation.isversionof | http://portal.acm.org/citation.cfm?id=314691 | |
dc.title | I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
kusw.oaversion | Scholarly/refereed, publisher version | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |