Computing a centerpoint of a finite planar set of points in linear time
From MaRDI portal
Publication:1338958
DOI10.1007/BF02574382zbMath0819.68137OpenAlexW2134711657MaRDI QIDQ1338958
Publication date: 27 November 1994
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131333
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Geometric constructions in real or complex geometry (51M15)
Related Items (21)
Approximate center points in dense point sets ⋮ Small strong epsilon nets ⋮ Multidimensional agreement in Byzantine systems ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Packing plane spanning trees into a point set ⋮ The complexity of hyperplane depth in the plane ⋮ Approximating Tverberg points in linear time for any fixed dimension ⋮ On strong centerpoints ⋮ Algorithms for bivariate zonoid depth ⋮ Intersecting convex sets by rays ⋮ Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions ⋮ Computational aspects of the colorful Carathéodory theorem ⋮ Centerpoints and Tverberg's technique ⋮ Computing the center region and its variants ⋮ Approximate centerpoints with proofs ⋮ Gathering in the plane of location-aware robots in the presence of spies ⋮ Balanced line separators of unit disk graphs ⋮ Small weak epsilon-nets ⋮ Extending the centerpoint theorem to multiple points ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Optimal Algorithms for Geometric Centers and Depth
Cites Work
This page was built for publication: Computing a centerpoint of a finite planar set of points in linear time
