On geometric optimization with few violated constraints
Discrete & Computational GeometryPublished 1 December 1995Open access
J Matousek
Citations120
SJR quartileQ2
SJR score0.60
SNIP1.04
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
We investigate the problem of finding the best solution satisfying all butk of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-calledLP-type problems. We give a general algorithm and discuss its efficient implementations for specific geometric problems. For instance for the problem of computing the smallest circle enclosing all butk of the givenn points in the plane, we obtain anO(n logn+k 3 n ε) algorithm; this improves previous results fork small compared withn but moderately growing. We also establish some results concerning general properties ofLP-type problems.
Keywords
Computer ScienceEngineering
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.
ACM Transactions on GraphicsSimulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
713 Citations1990Herbert Edelsbrunner, Ernst P. Mücke
This paper describes a general-purpose programming technique, called Simulation of Simplicity, that can be used to cope with degenerate input data for geometric algorithms and it is believed that this technique will become a standard tool in writing geometric software.
Discrete & Computational GeometryApplications of random sampling in computational geometry, II
664 Citations1989Kenneth L. Clarkson, Peter W. Shor
Journal of Computer and System SciencesMaintenance of configurations in the plane
462 Citations1981Mark H. Overmars, Jan Van Leeuwen
A fully dynamic maintenance algorithm for convex hulls that can process insertions and deletions of single points in only O(log* n) steps per transaction, where n is the number of points currently in the set.
Discrete & Computational GeometryNew applications of random sampling in computational geometry
317 Citations1987Kenneth L. Clarkson
This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry by creating a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer.
Lecture notes in computer scienceA combinatorial bound for linear programming and related problems
189 Citations1992Micha Sharir, Emo Welzl
A simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(d32 d n) time, and holds for any input.
Theoretical Computer ScienceThe densest hemisphere problem
159 Citations1978David Johnson, F. P. Preparata
A discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary and there exists a polynomial time algorithm which solves the problem in time O( n d −1 log n ) on a random access machine with unit cost arithmetic operations.
A subexponential randomized simplex algorithm (extended abstract)
141 Citations1992Gil Kalai
A randomized variant of the simplex algcrrithm, where C is an absolute constant, is described and the expected number of arithmetic operations required is at most min{n C.-, ~2Cwd&d }.
Journal of AlgorithmsFinding k points with minimum diameter and related problems
138 Citations1991Alok Aggarwal, Hiroshi Imai +2 more
This work considers the problem of finding k points of S that form a “small” set under some given measure, and presents efficient algorithms for several natural measures including the diameter and the variance.
SIAM Journal on ComputingOn <i>k</i>-Hulls and Related Problems
137 Citations1987Richard Cole, Micha Sharir +1 more
AlgorithmicaDynamic half-space range reporting and its applications
123 Citations1995Pankaj K. Agarwal, J. Matoušek
An O(n1+ɛ)-time algorithm for computing convex layers in ℝ3, and an output sensitive algorithm for Computing a level in an arrangements of planes in ™3, whose time complexity is O((b+n) nɛ, whereb is the size of the level.
Discrete & Computational GeometryIterated nearest neighbors and finding minimal polytopes
121 Citations1994David Eppstein, Jeff Erickson
A new method for finding several types of optimalk-point sets, minimizing perimeter, diameter, circumradius, and related measures, by testing sets of theO(k) nearest neighbors to each point, which is better in a number of ways than previous algorithms, which were based on high-order Voronoi diagrams.
A subexponential bound for linear programming
120 Citations1992Jiřı́ Matoušek, Micha Sharir +1 more
Mathematics of Operations ResearchThe Weighted Euclidean 1-Center Problem
98 Citations1983Nimrod Megiddo
An O(n(log n)3(log log n)2) algorithm for the problem of finding a point (x, y) in the plane that minimizes the maximal weighted distance to a point in a set of n given points is presented.
Journal of Computer and System SciencesA geometric consistency theorem for a symbolic perturbation scheme
92 Citations1990Chee-Keng Yap
The concept of an infinitesimal perturbation is introduced and it is shown that the method is consistent relative to such perturbations.
A Las Vegas algorithm for linear programming when the dimension is small
85 Citations1988Kenneth L. Clarkson
An algorithm for solving linear programming problems and the expected number of arithmetic operations required, with respect to the random choices made by the algorithm, are given.
Linear optimization queries
80 Citations1992Jiřı́ Matoušek, Otfried Schwarzkopf
An improved algorithm for computing the extreme points of an n-point set P in Ed, improved output-sensitive computation of convex hulls and Voronoi diagrams, and a Monte-Carlo algorithm for estimating the volume of a convex polyhedron given by the set of its vertices (in a fixed dimension).
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.
Computational GeometryComputing the smallest k-enclosing circle and related problems
77 Citations1994Alon Efrat, Micha Sharir +1 more
An efficient algorithm for solving the “smallest k-enclosing circle” (kSC) problem: Given a set of n points in the plane and an integer k ≤ n, find the smallest disk containing k of the points.
Discrete & Computational GeometryHelly-type theorems and Generalized Linear Programming
75 Citations1994Nina Amenta
It is shown that there is a Helly-type theorem about the constraint set of every Generalized Linear-Programming problem, which leads to many applications, including linear expected time algorithms for finding line transversals and mini-max hyperplane fitting.
Discrete & Computational GeometryPoints and triangles in the plane and halving planes in space
68 Citations1991Boris Aronov, Bernard Chazelle +4 more
Discrete & Computational GeometryCounting triangle crossings and halving planes
66 Citations1994Tamal K. Dey, Herbert Edelsbrunner
Journal of AlgorithmsStatic and Dynamic Algorithms for k-Point Clustering Problems
64 Citations1995Amitava Datta, Hans‐Peter Lenhof +2 more
A unified approach is given for solving the problem of finding a subset of S of size k that minimizes some closeness measure, such as the diameter, perimeter or the circumradius.
Information Processing LettersOn enclosing k points by a circle
56 Citations1995Jiřı́ Matoušek
This paper presents randomized algorithms for finding a smallest circle enclosing at least k points of P in the plane and an integer k ⩽ n, which improves on previous results by logarithmic factors.
An efficient approach to removing geometric degeneracies
44 Citations1992Ioannis Z. Emiris, John Canny
A variant scheme for a restricted class of algorithms that is asymptotically optimal with respect to the algebraic as well as the bit complexity and conform to certain criteria ensuring that the solution to the original input can be restored from the output on the perturbed input.
Lecture notes in computer scienceStatic and dynamic algorithms for k-point clustering problems
29 Citations1993Amitava Datta, Hans‐Peter Lenhof +2 more
Discrete & Computational GeometryA bound on local minima of arrangements that implies the upper bound theorem
27 Citations1993Kenneth L. Clarkson
The Upper Bound Theorem is obtained as a corollary, giving yet another proof of this celebrated bound on the number of vertices of a simple polytope inEd withn facets.
Lecture notes in computer scienceThe nature and meaning of perturbations in geometric computing
27 Citations1994Raimund Seidel
P perturbations are defined to be curves, it is pointed out that computing with them amounts to computing with limits, and methods of computing with such limits automatically are derived.
Helly theorems and generalized linear programming
26 Citations1995Annamaria Beatrice Amenta
A subexponential algorithm for abstract optimization problems
21 Citations1992Bernd Gärtner
The author presents a randomized algorithm that solves any AOP with an expected number of O(e/sup O( square root mod H mod )/) oracle calls, which gives the first subexponential bound in d for this problem.
Symposium on Discrete AlgorithmsIterated nearest neighbors and finding minimal polytypes
21 Citations1993David Eppstein, Jeff Erickson
Constructing levels in arrangements and higher order Voronoi diagrams
20 Citations1994Pankaj K. Agarwal, Mark de Berg +2 more
A simple lazy randomized incremental algorithm is given to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangement of planes in three-dimensional space.
Dehn-Sommerville relations, upper bound theorem, and levels in arrangements
12 Citations1993Ketan Mulmuley
It is shown that the invariance of the 0-th row and column of the h-matrix is invariant with respect to the defining linear function, and that the Dehn-Sommerville relations and McMullen's Upper Bound Theorem forconvex polytopes follow from the invariances of this matrix.
Lecture notes in computer scienceComputing the smallest k-enclosing circle and related problems
11 Citations1993Alon Efrat, Micha Sharir +1 more
An optimal algorithm for the (<i>≤ k</i>)-levels, with applications to separation and transversal problems
10 Citations1993Hazel Everett, Jean–Marc Robert +1 more
An optimal time algorithm is given for constructing the levels 1,…, k in an arrangement of lines in the plane and these algorithms can be used to solve the following separation and transversal problems.