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.

Computational geometry, Geographic information systems, Planar subdivisions, Vertex enumeration
dx.doi.org/10.1142/S0218195902000906
International Journal of Computational Geometry and Applications
School of Computer Science

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