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

DOI10.1137/0222077zbMath0799.68182OpenAlexW2060544933MaRDI QIDQ4277544

Jack Scott Snoeyink, Bernard Chazelle, Leonidas J. Guibas, Herbert Edelsbrunner, 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

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

Related Items

An introduction to randomization in computational geometry, Almost tight upper bounds for the single cell and zone problems in the three dimensions, 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, COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS, Robot motion planning and the single cell problem in arrangements