Rectilinear decompositions with low stabbing number

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    17 Citaten (Scopus)

    Samenvatting

    Let be a rectilinear polygon. The stabbing number of a decomposition of into rectangles is the maximum number of rectangles intersected by any axis-parallel segment that lies completely inside . We prove that any simple rectilinear polygon with n vertices admits a decomposition with stabbing number O(logn), and we give an example of a simple rectilinear polygon for which any decomposition has stabbing number O (logn). We also show that any rectilinear polygon with k 1 rectilinear holes and n vertices in total admits a decomposition with stabbing number O(vk logn). When the holes are rectangles, then a decomposition exists with stabbing number O(vk+logn), which we show is tight. All of these decompositions consist of O(n) rectangles.
    Originele taal-2Engels
    Pagina's (van-tot)215-221
    TijdschriftInformation Processing Letters
    Volume52
    Nummer van het tijdschrift4
    DOI's
    StatusGepubliceerd - 1994

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Rectilinear decompositions with low stabbing number'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit