Point Location in Arrangements of Hyperplanes
Information and ComputationPublished 1 October 1993
Stefan Meiser
Citations158
SJR quartileQ2
SJR score0.49
SNIP0.88
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.
TL;DR
A solution to the point location problem in arrangements of hyperplanes in Ed with running time O(d5 log n) and space O(nd+?) for arbitrary ? > 0, where n is the number ofhyperplanes.
Abstract
We present a solution to the point location problem in arrangements of hyperplanes in Ed with running time O(d5 log n) and space O(nd+κ) for arbitrary κ > 0, where n is the number of hyperplanes. The main result is the d5 factor in the expression for the running time. All previously known algorithms are exponential in d or log n. This leads to nonuniform polynomial algorithms for NP-complete problems.
Keywords
Computer ScienceEngineering
American Mathematical MonthlyAlgorithms in Combinatorial Geometry.
1,801 Citations1989Jacob E. Goodman, Herbert Edelsbrunner
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.
Discrete & Computational Geometryɛ-nets and simplex range queries
731 Citations1987David Haussler, Emo Welzl
The concept of an ɛ-net of a set of points for an abstract set of ranges is introduced and sufficient conditions that a random sample is an Â-net with any desired probability are given.
SIAM Journal on ComputingMultidimensional Searching Problems
249 Citations1976David Dobkin, Richard J. Lipton
Classic binary search is extended to multidimensional search problems and yields efficient algorithms for a number of tasks such as a secondary searching problem of Knuth, region location in planar graphs, and speech recognition.
How to net a lot with little: small ε-nets for disks and halfspaces
105 Citations1990Jiřı́ Matoušek, Raimund Seidel +1 more
It is shown that disks and pseudo-disks in the plane as well as halfspaces in R, which is best possible up to a multiplicative constant, allow-nets of size only &Ogr;(1/1/ε</italic)), which isbest possibleup to amultiplicative constant.
Journal of the ACMA Polynomial Linear Search Algorithm for the <i>n</i> -Dimensional Knapsack Problem
83 Citations1984Friedhelm Meyer auf der Heide
A probabilistic algorithm for the post office problem
45 Citations1985Kenneth L. Clarkson
The algorithm employs random sampling, so the expected time holds for any set of points, and approaches the preprocessing time required for any algorithm constructing the Voronoi diagram of the input points.
A deterministic algorithm for partitioning arrangements of lines and its application
28 Citations1989Pankaj K. Agarwal
This paper presents a deterministic algorithm which is faster than Matousk's recent algorithm [Ma] for large values of r, and applies it to several problems involving lines or segments in the plane, and obtain deterministic algorithms which are faster than any previously known algorithms.
Lecture notes in computer scienceOn genuinely time bounded computations
13 Citations2005Friedhelm Meyer auf der Heide
In this paper genuine complexity classes for given operation sets S are defined, following ideas due to Karpinski and the author from [KaM 88], and results on genuine computability, lower bound methods, as well as examples for complexity gaps and separated complexity classes are surveyed.