On approximating the depth and related problems

Boris Aronov; Sariel Har-Peled

On approximating the depth and related problems

Boris Aronov, Sariel Har-Peled

Research output: Contribution to conference › Paper › peer-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 language	English (US)
Pages	886-894
Number of pages	9
State	Published - 2005
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005

Other

Other	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Vancouver, BC
Period	1/23/05 → 1/25/05

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{6a9384f63f19406ea137d5acb047db5f,

title = "On approximating the depth and related problems",

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.",

author = "Boris Aronov and Sariel Har-Peled",

year = "2005",

language = "English (US)",

pages = "886--894",

note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

T1 - On approximating the depth and related problems

AU - Aronov, Boris

AU - Har-Peled, Sariel

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=20744455809&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20744455809&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:20744455809

SP - 886

EP - 894

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

On approximating the depth and related problems

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this