Two-dimensional and three-dimensional point location in rectangular subdivisions

M. Berg, de, M.J. Kreveld, van, J. Snoeyink

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    29 Citaten (Scopus)
    1 Downloads (Pure)


    We apply van Emde Boas-type stratified trees to point location problems in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0, U - 1], we locate an integer query point in O((log log U)d) query time using O(n) space when d = 2 or O(n log log U) space when d = 3. Applications and extensions of this "fixed universe" approach include spatial point location using logarithmic time and linear space in rectilinear subdivisions having arbitrary coordinates, point location in c-oriented polygons or fat triangles in the plane, point location in subdivisions of space into "fat prisms," and vertical ray shooting among horizontal "fat objects." Like other results on stratified trees, our algorithms run on a RAM model and make use of perfect hashing.
    Originele taal-2Engels
    Pagina's (van-tot)256-277
    Aantal pagina's22
    TijdschriftJournal of Algorithms
    Nummer van het tijdschrift2
    StatusGepubliceerd - 1995

    Vingerafdruk Duik in de onderzoeksthema's van 'Two-dimensional and three-dimensional point location in rectangular subdivisions'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit