On approximating the depth and related problems

Boris Aronov, Sariel Har-Peled

    Research output: Contribution to conferencePaperpeer-review


    In this paper, we study the problem of finding a disk covering the largest number of red points, while avoiding all the blue points. We reduce it to the question of finding a deepest point in an arrangement of pseudodisks and provide a near-linear expected-time randomized approximation algorithm for this problem. As an application of our techniques, we show how to solve linear programming with violations approximately. We also prove that approximate range counting has roughly the same time and space complexity as answering emptiness range queries.

    Original languageEnglish (US)
    Number of pages9
    StatePublished - 2005
    EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
    Duration: Jan 23 2005Jan 25 2005


    OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
    Country/TerritoryUnited States
    CityVancouver, BC

    ASJC Scopus subject areas

    • Software
    • General Mathematics


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

    Cite this