On levels in arrangements and voronoi diagrams
Discrete & Computational GeometryPublished 1 September 1991Open access
Ketan Mulmuley
Citations78
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.
TL;DR
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.
Abstract
This paper gives efficient, randomized algorithms for the following problems: (1) construction of levels of order 1 tok in an arrangement of hyperplanes in any dimension and (2) construction of higher-order Voronoi diagrams of order 1 tok in any dimension. A new combinatorial tool in the form of a mathematical series, called a θ series, is associated with an arrangement of hyperplanes inR d . It is used to study the combinatorial as well as algorithmic complexity of the geometric problems under consideration.
Keywords
Computer ScienceEngineering
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
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.
SIAM Journal on ComputingConstructing Arrangements of Lines and Hyperplanes with Applications
444 Citations1986Herbert Edelsbrunner, Joseph O’Rourke +1 more
Discrete & Computational GeometryVoronoi diagrams and arrangements
349 Citations1986Herbert Edelsbrunner, Raimund Seidel
IEEE Transactions on ComputersOn k-Nearest Neighbor Voronoi Diagrams in the Plane
321 Citations1982Der-Tsai Lee
It is shown that the k-nearest neighbor problem and other seemingly unrelated problems can be solved efficiently with the Voronoi diagram.
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.
Information Processing LettersVoronoi diagrams from convex hulls
283 Citations1979Kevin Q. Brown
The fundamental result is that a K-dimensional Euclidean Voronoi diagram of N points can be constructed by transforming the points to K + I-space, which extends straightforwardly to higher dimensions.
Elsevier eBooksDissection Graphs of Planar Point Sets
179 Citations1973Péter L. Erdős, László Lovász +2 more
A fast planar partition algorithm. I
105 Citations1988Ketan Mulmuley
Though the algorithm itself is simple, the global evolution of the partition is complex, which makes the analysis of the algorithm theoretically interesting in its own right.
Journal of Combinatorial Theory Series AThe number of small semispaces of a finite set of points in the plane
96 Citations1986Noga Alon, Ervin Győri
A Linear time algorithm for computing the Voronoi diagram of a convex polygon
68 Citations1987Alok Aggarwal, Leonidas Guibas +2 more
An algorithm is presented for computing certain kinds of three-dimensional convex hulls in linear time and it is shown that the Voronoi diagram ofn sites in the plane can be computed in Θ(n) time when these sites form the vertices of a convex polygon in counterclockwise order.
Discrete & Computational GeometryHalfspace range search: An algorithmic application ofk-sets
63 Citations1986Bernard Chazelle, F. P. Preparata
It is shown that the total number ofj-sets realized by a set ofn points inE3 isO(nk5); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.
Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental
54 Citations1988Kenneth L. Clarkson, Peter W. Shor
An algorithm of this kind is given for computing the intersection of a set of halfspaces in three dimensions, resulting in a Las Vegas algorithm for the diameter requiring n expected time.
An efficient algorithm for hidden surface removal
54 Citations1989Ketan Mulmuley
An efficient, randomized hidden surface removal algorithm, with the best time complexity so far, which provably holds for any input, regardless of the way in which faces are located in the scene.
Discrete & Computational GeometryMore onk-sets of finite sets in the plane
54 Citations1986Emo Welzl
It is shown that there is a positive constantc such thatfK(S) is the number of subsets of S with cardinalityk εK which can be cut offS by a straight line.
AlgorithmicaEdge-skeletons in arrangements with applications
43 Citations1986Herbert Edelsbrunner
A method is given that constructs a skeleton inO(√n logn) time per edge that implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams in E2 and space cutting trees in E3.
Journal of Combinatorial Theory Series AOn the number of k-subsets of a set of n points in the plane
43 Citations1984Jacob E. Goodman, Richard Pollack
By generalizing to a combinatorial problem, it is shown that for 2 k n the number of sets of size at most k is at most 2 nk − 2 k 2 − k.
On k-hulls and related problems
42 Citations1984Richard Cole, Micha Sharir +1 more
Efficient computation of the 'cut' guaranteed by the classical 'Ham Sandwich theorem', faster preprocessing time for polygon retrieval, and theoretical improvements to a problem of intersecting lines and points posed by Hopcroft.
Journal of the ACMA fast planar partition algorithm, II
36 Citations1991K. Mulmuley
A new technique for clipping is provided, called virtual clipping, whose overhead per window W depends logarithmically on the number if intersections between the borders of W and the input segments, in contrast to the overhead of the conventional clipping technique.
ACM SIGGRAPH Computer GraphicsAn efficient algorithm for hidden surface removal
36 Citations1989K. Mulmuley
A fast planar partition algorithm, II
19 Citations1989Ketan Mulmuley
A new technique for clipping is provided, called virtual clipping, whose overhead per window W depends logarithmically on the number if intersections between the borders of W and the input segments, in contrast to the overhead of the conventional clipping technique.
An improved algorithm for constructing <i>k</i><sup>th</sup>-order Voronoi diagrams
16 Citations1985Bernard Chazelle, Herbert Edelsbrunner
The kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E2 subdivides into maximal regions such that all points within a given region have the same k nearest sites.
On obstructions in relation to a fixed viewpoint
14 Citations1989Ketan Mulmuley
Efficient, randomized algorithms are given for the construction of levels of order 1 to k in an arrangement of hyperplanes in any dimension and hidden surface removal for completely general scenes.