New results on binary space partitions in the plane

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    21 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)317-333
    Aantal pagina's17
    TijdschriftComputational Geometry
    Volume8
    Nummer van het tijdschrift6
    DOI's
    StatusGepubliceerd - 1997

    Vingerafdruk

    Duik in de onderzoeksthema's van 'New results on binary space partitions in the plane'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit