SIAM Journal on Computing · 2000 · 32 citations · 19 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryGeometric ConstructionsRandomized Geometric AlgorithmsArrangement Of Line SegmentsCutting PlanesCuttingsLine Segment ArrangementsRandomized Incremental ConstructionRandomized Line Arrangement AlgorithmsUpper Bound Computation
We present several variants of a new randomized incremental algorithm for computing a cutting in an arrangement of n lines in the plane. The algorithms produce cuttings whose expected size is O(r2 ), and the expected running time of the algorithms is O(nr). Both bounds are asymptotically optimal for nondegenerate arrangements. The algorithms are also simple to implement, and we present empirical results showing that they perform well in practice. We also present another efficient algorithm (with slightly worse time bound) that generates small cuttings whose size is guaranteed to be close to the best known upper bound of J. Matou{s}ek [Discrete Comput. Geom., 20 (1998), pp. 427--448].
19
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
Applications of random sampling in computational geometry, II
Kenneth L. Clarkson · 1988 · 943 citations · Full text
ɛ-nets and simplex range queries
David Haussler, Emo Welzl · Discrete & Computational Geometry · 1987 · 731 citations · Full text