On lazy randomized incremental construction

M. Berg, de, K.T.G. Dobrindt, O. Schwarzkopf

    Research output: Contribution to journalArticleAcademicpeer-review

    42 Citations (Scopus)

    Abstract

    We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, theselazy randomized incremental algorithms are suited for computing structures that have a "nonlocal" definition. In order to analyze these algorithms we generalize some results on random sampling to such situations. We apply our techniques to obtain efficient algorithms for the computation of single cells in arrangements of segments in the plane, single cells in arrangements of triangles in space, and zones in arrangements of hyperplanes.
    Original languageEnglish
    Pages (from-to)261-286
    JournalDiscrete and Computational Geometry
    Volume14
    DOIs
    Publication statusPublished - 1995

    Fingerprint

    Dive into the research topics of 'On lazy randomized incremental construction'. Together they form a unique fingerprint.

    Cite this