An optimal algorithm for the boundary of a cell in a union of rays
From MaRDI portal
Publication:911755
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)
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
