Computing a Face in an Arrangement of Line Segments and Related Problems

DOI10.1137/0222077MaRDI QIDQ4277544zbMATH OpenOpenAlexFDO

Authors Jack Snoeyink, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir

Publication date 24 February 1994

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

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

zbMATH Keywords

arrangementscomputational geometryDavenport-Schinzel sequencesrandomized incremental algorithmsprobabilistic backwards analysis

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Real and complex geometry (51M99)

Recommendations

• Computing Many Faces in Arrangements of Lines and Segments
• The complexity and construction of many faces in arrangements of lines and of segments
• scientific article; zbMATH DE number 1263244
• A fast planar partition algorithm. I
• On lazy randomized incremental construction

Cited in

(26)

• On lazy randomized incremental construction
• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
• scientific article; zbMATH DE number 1445368 (Why is no real title available?)
• The number of edges of many faces in a line segment arrangement
• COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
• On computing connected components of line segments
• A fast planar partition algorithm. I
• Computing a single cell in the overlay of two simple polygons
• Constructing many faces in arrangements of lines and segments
• A fast planar partition algorithm, II
• Describing faces in plane triangulations
• Implicitly representing arrangements of lines or segments
• scientific article; zbMATH DE number 742952 (Why is no real title available?)
• The complexity and construction of many faces in arrangements of lines and of segments
• On lazy randomized incremental construction
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE
• The complexity of the outer face in arrangements of random segments
• Segments in enumerating faces
• On k-enclosing slab problems
• An introduction to randomization in computational geometry
• Robot motion planning and the single cell problem in arrangements
• Almost tight upper bounds for the single cell and zone problems in the three dimensions
• Rounding Arrangements Dynamically
• Arrangements of segments that share endpoints: Single face results
• On Computing the Centroid of the Vertices of an Arrangement and Related Problems

This page was built for publication: Computing a Face in an Arrangement of Line Segments and Related Problems

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