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.
@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}
}