On the number of line separations of a finite set in the plane

DOI10.1016/0097-3165(85)90017-2zbMath0616.52003OpenAlexW1974343573WikidataQ54310000 ScholiaQ54310000MaRDI QIDQ1821352

Herbert Edelsbrunner, Ermo Welzl

Publication date: 1985

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(85)90017-2

zbMATH Keywords

Euclidean planek-set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Inequalities and extremum problems involving convexity in convex geometry (52A40) Other problems of combinatorial convexity (52A37) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

Diameter partitioning, On the expected number of \(k\)-sets, More on k-sets of finite sets in the plane, Voronoi diagrams and arrangements, The number of extreme pairs of finite point-sets in Euclidean spaces, Edge-skeletons in arrangements with applications, Cutting dense point sets in half, On the two-dimensional Davenport-Schinzel problem, Line arrangements and range search, Long non-crossing configurations in the plane, Dense point sets with many halving lines, The complexity of point configurations, Points and triangles in the plane and halving planes in space, An upper bound on the number of planar \(K\)-sets, On the average number of \(k\)-sets, A polynomial-time algorithm for computing the yolk in fixed dimension, New applications of random sampling in computational geometry, Semispaces of configurations, cell complexes of arrangements, Arrangements of oriented hyperplanes, \(k\)-sets and random hulls

Cites Work

• Teilungen der Ebenen durch Geraden oder topologische Geraden
• On the combinatorial classification of nondegenerate configurations in the plane
• Polygonal intersection searching
• Polygon Retrieval
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item