An optimal algorithm for the boundary of a cell in a union of rays

DOI10.1007/BF01840405zbMath0697.68030MaRDI QIDQ911755

Franco P. Preparata, Jean-Daniel Boissonnat, Panagiotis D. Alevizos

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

combinatorial geometrycomputational geometryunion of half-lines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Discrete mathematics in relation to computer science (68R99)

Related Items

Arrangements of segments that share endpoints: Single face results, An optimal algorithm for the boundary of a cell in a union of rays - Corrigendum, The common exterior of convex polygons in the plane, Computing depth orders for fat objects and related problems, Enumerating Davenport-Schinzel sequences, On the boundary of a union of Rays, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Weighted Voronoi Diagrams in the Maximum Norm, Robot motion planning and the single cell problem in arrangements, On the zone of the boundary of a convex body, On the union of fat wedges and separating a collection of segments by a line

Cites Work

• The complexity and construction of many faces in arrangements of lines and of segments
• Visibility and intersection problems in plane geometry
• The power of geometric duality
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Separating two simple polygons by a sequence of translations
• On the general motion-planning problem with two degrees of freedom
• Constructing Arrangements of Lines and Hyperplanes with Applications