Simple traversal of a subdivision without extra storage

M. Berg, de, M.J. Kreveld, van, R. Oostrum, van, M.H. Overmars

    Research output: Contribution to journalArticleAcademicpeer-review

    34 Citations (Scopus)


    In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth-first search on the subdivision, using local criteria for deciding what is the next cell to visit. Our method is extremely simple and provably correct. The algorithm has applications in the field of geographic information systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible. We show how to adapt our algorithm to answer related queries, such as windowing queries and reporting connected subsets of cells that have a common attribute. Finally, we show how to extend our algorithm such that it can handle convex threedimensional subdivisions.
    Original languageEnglish
    Pages (from-to)359-373
    JournalInternational Journal of Geographical Information Science
    Issue number4
    Publication statusPublished - 1997


    Dive into the research topics of 'Simple traversal of a subdivision without extra storage'. Together they form a unique fingerprint.

    Cite this