Pseudo-Line Arrangements: Duality, Algorithms, and Applications

DOI10.1137/S0097539703433900zbMath1077.52516MaRDI QIDQ5317163

Micha Sharir, Pankaj K. Agarwal

Publication date: 16 September 2005

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

zbMATH Keywords

arrangementsdualitypseudo-lines

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Related Items

A crossing lemma for Jordan curves ⋮ On the geometric priority set cover problem ⋮ On the number of simple arrangements of five double pseudolines ⋮ Ham-sandwich cuts for abstract order types ⋮ On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves ⋮ Parallelogram tilings, worms, and finite orientations ⋮ On the complexity of the \(k\)-level in arrangements of pseudoplanes ⋮ Unnamed Item ⋮ On regular vertices of the union of planar convex objects ⋮ Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications