On approximating the depth and related problems

Boris Aronov, Sariel Har-Peled

    Research output: Contribution to conferencePaper

    Abstract

    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)
    Pages886-894
    Number of pages9
    StatePublished - 2005
    EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
    Duration: Jan 23 2005Jan 25 2005

    Other

    OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
    CountryUnited States
    CityVancouver, BC
    Period1/23/051/25/05

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

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

  • Cite this

    Aronov, B., & Har-Peled, S. (2005). On approximating the depth and related problems. 886-894. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.