On approximating the depth and related problems

Boris Aronov, Sariel Har-Peled

    Research output: Contribution to journalArticle

    Abstract

    We study the question of finding a deepest point in an arrangement of regions and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when the deepest point is shallow. This implies, among other results, a fast algorithm for approximately solving linear programming problems with violations. We also use this technique to approximate the disk covering the largest number of red points, while avoiding all the blue points, given two such sets in the plane. Using similar techniques implies that approximate range counting queries have roughly the same time and space complexity as emptiness range queries.

    Original languageEnglish (US)
    Pages (from-to)899-921
    Number of pages23
    JournalSIAM Journal on Computing
    Volume38
    Issue number3
    DOIs
    StatePublished - 2008

    Keywords

    • Approximation
    • Computational geometry
    • Randomized algorithms

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'On approximating the depth and related problems'. Together they form a unique fingerprint.

  • Cite this