New results on binary space partitions in the plane

M. Berg, de, M.M. Groot, de, M.H. Overmars

    Research output: Contribution to journalArticleAcademicpeer-review

    21 Citations (Scopus)

    Abstract

    We prove the existence of linear size binary space partitions for sets of objects in the plane under certain conditions. In particular, we construct linear size binary space partitions for sets of fat objects, for sets of line segments where the ratio between the lengths of the longest and shortest segment is bounded by a constant, and for homothetic objects. For all cases we also show how to turn the existence proofs into efficient algorithms.
    Original languageEnglish
    Pages (from-to)317-333
    Number of pages17
    JournalComputational Geometry
    Volume8
    Issue number6
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'New results on binary space partitions in the plane'. Together they form a unique fingerprint.

  • Cite this