Lines in space: Combinatorics and algorithms

DOI10.1007/BF01955043zbMath0846.68098MaRDI QIDQ1913699

Leonidas J. Guibas, Bernard Chazelle, Herbert Edelsbrunner, Jorge Stolfi, Micha Sharir

Publication date: 27 May 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

computational geometry

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items

On range searching with semialgebraic sets, On joints in arrangements of lines in space and related problems, Almost tight upper bounds for lower envelopes in higher dimensions, Configuration spaces of spatial linkages: Taking Collisions Into Account, Generalized hidden surface removal, Point location in zones of \(k\)-flats in arrangements, On Ray Shooting for Triangles in 3-Space and Related Problems, On the complexity of sets of free lines and line segments among balls in three dimensions, Improved Bounds for Incidences Between Points and Circles, Partitioning arrangements of lines. II: Applications, REGION INTERVISIBILITY IN TERRAINS, Ray shooting and intersection searching amidst fat convex polyhedra in 3-space, Bisecting three classes of lines, Finding stabbing lines in 3-space, Counting and cutting cycles of lines and rods in space, Applications of a new space-partitioning technique, The power of parallel projection, Ray shooting and stone throwing with near-linear storage, The union of moving polygonal pseudodiscs -- combinatorial bounds and applications, Clamshell casting, Crossing patterns of semi-algebraic sets, Algorithms for bichromatic line-segment problems and polyhedral terrains

Cites Work

• The complexity and construction of many faces in arrangements of lines and of segments
• The complexity of many cells in arrangements of planes and related problems
• A deterministic view of random sampling and its use in geometry
• Construction of \(\epsilon\)-nets
• Combinatorial complexity bounds for arrangements of curves and spheres
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplane arrangements
• On \(k\)-sets in arrangements of curves and surfaces
• Counting and cutting cycles of lines and rods in space
• On joints in arrangements of lines in space and related problems
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Weaving patterns of lines and line segments in space
• On the Betti Numbers of Real Varieties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item