Separating and shattering long line segments

DOI10.1016/S0020-0190(97)00188-9zbMath1338.68262MaRDI QIDQ293158

Alon Efrat, Otfried Schwarzkopf

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097001889?np=y

zbMATH Keywords

computational geometryBSP-treesline separation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (2)

Shattering a set of objects in 2D ⋮ LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS

Cites Work

• The complexity and construction of many faces in arrangements of lines and of segments
• Topologically sweeping an arrangement
• Applications of random sampling to on-line algorithms in computational geometry
• On the union of fat wedges and separating a collection of segments by a line
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• On a class of \(O(n^ 2)\) problems in computational geometry
• Applications of a semi-dynamic convex hull algorithm
• On lazy randomized incremental construction

This page was built for publication: Separating and shattering long line segments