Computing Many Faces in Arrangements of Lines and Segments

DOI10.1137/S009753979426616XMaRDI QIDQ4388883zbMATH OpenOpenAlexWikidataFDO

Authors Pankaj K. Agarwal, Jiří Matoušek, Otfried Cheong

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979426616x

zbMATH Keywords

arrangementsdualityrandom sampling

Mathematics Subject Classification ID

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

Recommendations

• Computing a Face in an Arrangement of Line Segments and Related Problems
• The complexity and construction of many faces in arrangements of lines and of segments
• scientific article; zbMATH DE number 1263244
• Implicitly representing arrangements of lines or segments

Cited in

(17)

• Segments in enumerating faces
• On separating points by lines
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Near-linear approximation algorithms for geometric hitting sets
• Computing a single cell in the overlay of two simple polygons
• From proximity to utility: a Voronoi partition of Pareto optima
• The complexity of the outer face in arrangements of random segments
• Describing faces in plane triangulations
• A note on visibility-constrained Voronoi diagrams
• A note about weak -nets for axis-parallel boxes in d-space
• Computing a Face in an Arrangement of Line Segments and Related Problems
• The complexity and construction of many faces in arrangements of lines and of segments
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• On lazy randomized incremental construction
• On lazy randomized incremental construction
• Constructing many faces in arrangements of lines and segments
• Lower envelopes of surface patches in 3-space

This page was built for publication: Computing Many Faces in Arrangements of Lines and Segments

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