On approximating the depth and related problems

Boris Aronov, Sariel Har-Peled

Research output: Contribution to conferencePaperpeer-review

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 - Jul 1 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
Country/TerritoryUnited 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