Applications of random sampling in computational geometry. II
type: Item
instance of: scholarly article
title: Applications of random sampling in computational geometry. II
zbMATH Open document ID: 0681.68060
DOI: 10.1007/BF02187740
author: Kenneth L. Clarkson
author: Peter W. Shor
published in: Discrete \& Computational Geometry
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131089
review text: The paper is an excellent overview about several ``Las Vegas''-algorithms given by the authors. Some results are improvements of results given by the first author in an earlier paper \textit{K.L. Clarkson} [Discrete Comput. Geom. 2, 195-222 (1987; Zbl 0615.68037)]. Random sampling is used for several new geometric algorithms. The central lemma formulated at the beginning gives sharp bounds for the use of random subsets. Such subsets can be used for divide and conquer and for some incremental techniques. Some interesting results and algorithms are the following: An 0(A \(+\) n log n)-expected time and 0(n)-space-algorithm reports all the A intersecting pairs of a set of n line segments in the plane. An 0(n log n)-expected time algorithm computes the convex hull of n points in \(E^ 3\) (for \(d>3:\) \(0(n^{\lfloor d/2\rfloor}))\). An 0(n log n)-expected time algorithm computes the diameter of a set of n points in \(E^ 3\). Algorithms for halfspace range reporting and a simple proof for bounds on high-order Voronoi diagrams are given. In the concluding remarks relations with deterministic algorithms and possible extensions are discussed.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 62D05
zbMATH DE Number: 4115965
zbMATH Keywords: computational geometry
zbMATH Keywords: Random sampling
zbMATH Keywords: convex hull
zbMATH Keywords: diameter
zbMATH Keywords: Voronoi diagrams
reviewed by: Hans-Dietrich Hecker
MaRDI profile type: Publication
cites work: The number of small semispaces of a finite set of points in the plane
cites work: An optimal algorithm for intersecting line segments in the plane
cites work: The power of geometric duality
cites work: Halfspace range search: An algorithmic application of k-sets
cites work: New applications of random sampling in computational geometry
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: A fast Las Vegas algorithm for triangulating a simple polygon
cites work: On k-Hulls and Related Problems
cites work: Q3772828
cites work: On the shape of a set of points in the plane
cites work: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
cites work: Constructing Arrangements of Lines and Hyperplanes with Applications
cites work: Q4065548
cites work: On the number of k-subsets of a set of n points in the plane
cites work: Q3939231
cites work: Primitives for the manipulation of general subdivisions and the computation of Voronoi
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Q3237947
cites work: Quicksort
cites work: The Ultimate Planar Convex Hull Algorithm?
cites work: Linear Programming in Linear Time When the Dimension Is Fixed
cites work: Finding the intersection of two convex polyhedra
cites work: Convex hulls of finite sets of points in two and three dimensions
cites work: Q3992847
cites work: Optimal randomized parallel algorithms for computational geometry
cites work: More on k-sets of finite sets in the plane
OpenAlex ID: W4254977685
Recommended article: An optimal convex hull algorithm in any fixed dimension
Recommended article: Q3138743
Recommended article: Applications of random sampling to on-line algorithms in computational geometry
Recommended article: Randomized incremental construction of Delaunay and Voronoi diagrams
Recommended article: Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
Recommended article: Q4038708
Recommended article: Q4230330
Recommended article: Randomized geometric algorithms and pseudorandom generators
Recommended article: An introduction to randomization in computational geometry
Recommended article: A fast Las Vegas algorithm for triangulating a simple polygon
description: scientific article; zbMATH DE number 4115965