Home Bookmarks Papers Blog

On Approximating the Depth and Related Problems

Boris Aronov and Sariel Har-Peled.


In this paper, we study the problem of finding the disk covering the largest number of red points, while avoiding all the blue points. We reduce it to the questions of finding the 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 show that approximate range counting has (roughly) the same time and space complexity as answering emptiness range queries.

PDF.


Talk slides
@string{SICOMP = "SIAM J. Comput."}

@article{ah-adrp-08,
  author       = {B. Aronov and S. {Har-Peled}},
  title        = {On Approximating the Depth and Related Problems},
  publisher    = {SIAM},
  year         = {2008},
  journal      = SICOMP,
  volume       = {38},
  number       = {3},
  pages        = {899--921}
}

Last modified: Wed Jun 2 04:29:09 CDT 2010