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

DOI10.1007/BF01840405MaRDI QIDQ911755zbMATH OpenFDO

Authors Jean-Daniel Boissonnat, F. P. Preparata, Panagiotis D. Alevizos

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

computational geometrycombinatorial geometryunion of half-lines

Mathematics Subject Classification ID

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

Recommendations

• An optimal algorithm for the boundary of a cell in a union of rays - Corrigendum
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• scientific article; zbMATH DE number 3804872
• scientific article; zbMATH DE number 437529
• scientific article; zbMATH DE number 176772

Cites work

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

Cited in

(12)

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

This page was built for publication: An optimal algorithm for the boundary of a cell in a union of rays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911755)