On approximating the depth and related problems
Symposium on Discrete AlgorithmsPublished 23 January 2005
Boris Aronov, Sariel Har-Peled
Citations46
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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.
Keywords
Computer Science
Neural network learning theoretical foundations
1,357 Citations2009Martin Anthony, Peter L. Bartlett
The authors explain the role of scale-sensitive versions of the Vapnik Chervonenkis dimension in large margin classification, and in real prediction, and discuss the computational complexity of neural network learning.
Applications of random sampling in computational geometry, II
932 Citations1988Kenneth L. Clarkson
Asymptotically tight bounds for (≤k)-sets are given, which are certain halfspace partitions of point sets, and a simple proof of Lee's bounds for high-order Voronoi diagrams is given.
Journal of AlgorithmsA linear algorithm for determining the separation of convex polyhedra
219 Citations1985David Dobkin, David Kirkpatrick
This work presents a linear algorithm for constructing a pair of points that realize the separation of two convex polyhedra in three dimensions based on a simple hierarchical description of polyhedRA that is of interest in its own right.
Discrete & Computational GeometryRange searching with efficient hierarchical cuttings
211 Citations1993Jiřı́ Matoušek
Lecture notes in computer scienceDetermining the separation of preprocessed polyhedra — A unified approach
194 Citations2005David Dobkin, David Kirkpatrick
The emphasis is the uniform treatment of polyhedra separation problems, the use of hierarchical representations of primitive objects to provide implicit representations of composite or transformed objects, and applications to natural problems in graphics and robotics.
SIAM Journal on ComputingFat Triangles Determine Linearly Many Holes
160 Citations1994Matousek Jiri, János Pach +3 more
The authors show that for every fixed $\delta>0$ the following holds: if $F$ is a union of triangles, all of whose angles are at least $delta$, then the complement of F has $O(n)$ connected components and the boundary of F consists of straight segments.
Computational GeometryApproximate range searching☆☆A preliminary version of this paper appeared in the Proc. of the 11th Annual ACM Symp. on Computational Geometry, 1995, pp. 172–181.
131 Citations2000Sunil Arya, David M. Mount
Discrete & Computational GeometryOn geometric optimization with few violated constraints
120 Citations1995J Matousek
On K-Sets in Arrangements of Curves and Surfaces
95 Citations2018Micha Sharir
Discrete & Computational GeometryOn levels in arrangements and voronoi diagrams
78 Citations1991Ketan Mulmuley
This paper gives efficient, randomized algorithms for the following problems: construction of levels of order 1 tok in an arrangement of hyperplanes in any dimension and construction of higher-order Voronoi diagrams of order1 tokIn any dimension.
Combinatorics Probability ComputingThe Clarkson–Shor Technique Revisited and Extended
31 Citations2003Micha Sharir
This work provides an alternative simpler and more general version of the Clarkson-Shor probabilistic technique and uses it to obtain in addition several extensions and new combi- natorial bounds.
How hard is halfspace range searching?
29 Citations1992Hervé Brönnimann, Bernard Chazelle
The first nontrivial lower bound for halfspace range searching is established and implies nontrivial lower bounds for spherical range searching in any fixed dimension.
Low-dimensional linear programming with violations
21 Citations2003Timothy M. Chan
A simple algorithm in 2-d that runs in O((n + k/sup 2/) log n) expected time is given; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matousek (1994) and is probably near-optimal for all k /spl Lt/ n/2.
When crossings count — approximating the minimum spanning tree
10 Citations2000Sariel Har-Peled, Piotr Indyk
An (1+\mu)-approximation algorithm to the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of crossings between the spanning tree and the lines, and how to embed such a crossing metric, into high-dimensions, so that the distances are preserved.