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(n2) 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.

Additional Metadata
Keywords Computational geometry, Geographic information systems, Planar subdivisions, Vertex enumeration
Persistent URL dx.doi.org/10.1142/S0218195902000906
Journal International Journal of Computational Geometry and Applications
Citation
Bose, P, & Morin, P. (2002). An improved algorithm for subdivision traversal without extra storage. In International Journal of Computational Geometry and Applications (Vol. 12, pp. 297–308). doi:10.1142/S0218195902000906