Simple traversal of a subdivision without extra storage

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    34 Citaties (SciVal)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)359-373
    TijdschriftInternational Journal of Geographical Information Science
    Nummer van het tijdschrift4
    StatusGepubliceerd - 1997


    Duik in de onderzoeksthema's van 'Simple traversal of a subdivision without extra storage'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit