Points and triangles in the plane and halving planes in space

DOI10.1007/BF02574700zbMath0764.68057OpenAlexW1987796943MaRDI QIDQ1176320

Boris Aronov, Bernard Chazelle, Micha Sharir, Leonidas J. Guibas, Rephael Wenger, Herbert Edelsbrunner

Publication date: 25 June 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131169

zbMATH Keywords

pointstriangleshalving planes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

On the expected number of \(k\)-sets, Algorithms for ham-sandwich cuts, Counting triangle crossings and halving planes, Overlap properties of geometric expanders, Dynamic half-space range reporting and its applications, Improved bounds on weak \(\varepsilon\)-nets for convex sets, Cutting dense point sets in half, A survey of mass partitions, On geometric optimization with few violated constraints, Point Selections and Weak ε-Nets for Convex Hulls, Berge's theorem, fractional Helly, and art galleries, On levels in arrangements of surfaces in three dimensions, Upper bounds for stabbing simplices by a line, An upper bound on the number of planar \(K\)-sets, Hitting and Piercing Rectangles Induced by a Point Set, Crossing-free segments and triangles in point configurations, Eppstein's bound on intersecting triangles revisited, Selection Lemmas for Various Geometric Objects, Median hyperplanes in normed spaces -- a survey, \(k\)-sets and random hulls

Cites Work

• Unnamed Item
• Unnamed Item
• On the number of k-subsets of a set of n points in the plane
• The number of small semispaces of a finite set of points in the plane
• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• On the number of line separations of a finite set in the plane
• Applications of random sampling in computational geometry. II
• On the number of halving planes
• Selecting Heavily Covered Points
• Power Diagrams: Properties, Algorithms and Applications