SIAM Journal on Computing · 1998 · 48 citations · 19 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryGeometric ApproximationGeometry ProcessingRandomized Geometric AlgorithmsArrangement Of Line SegmentsFaces In ArrangementsLine ArrangementsRandomized Line Arrangement Algorithms
We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized $O(n \log n)$ expected time algorithm for computing $\sqrt{n}$ cells in an arrangement of n lines.
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
Extremal problems in discrete geometry
Endre Szemerédi, W. T. Trotter · COMBINATORICA · 1983 · 556 citations