We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An Improved Algorithm for Subdivision Traversal without Extra Storage.
- Authors
Bose, Prosenjit; Morin, Pat; Tokuyama, T.
- Abstract
We describe an algorithm for enumerating all vertices, edges and faces of a planar subdivision stored in any of the usual pointer-based representations, while using only a constant amount of memory beyond that required to store the subdivision. The algorithm is a refinement of a method introduced by de Berg et al (1997), that reduces the worst case running time from O(n²) to O(n log n). We also give experimental results that show that our modified algorithm runs faster not only in the worst case, but also in many realistic cases.
- Subjects
ALGORITHMS; GEOGRAPHIC information systems; GEOMETRY
- Publication
International Journal of Computational Geometry & Applications, 2002, Vol 12, Issue 4, p297
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195902000906