Rectilinear decompositions with low stabbing number

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

    Research output: Contribution to journalArticleAcademicpeer-review

    17 Citations (Scopus)


    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.
    Original languageEnglish
    Pages (from-to)215-221
    JournalInformation Processing Letters
    Issue number4
    Publication statusPublished - 1994


    Dive into the research topics of 'Rectilinear decompositions with low stabbing number'. Together they form a unique fingerprint.

    Cite this