Computing a centerpoint of a finite planar set of points in linear time

DOI10.1007/BF02574382MaRDI QIDQ1338958zbMATH OpenOpenAlexFDO

Authors V. Pereyra

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

zbMATH Keywords

linear-time algorithmcenterpoint

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Geometric constructions in real or complex geometry (51M15)

Recommendations

• Publication:3359798
• Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
• COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON
• Computing a Segment Center for a Planar Point Set

Cites work

• scientific article; zbMATH DE number 3160756 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• On k-Hulls and Related Problems
• Partitioning with two lines in the plane
• Slowing down sorting networks to obtain faster sorting algorithms

Cited in

(30)

• A linear time deterministic algorithm to find a small subset that approximates the centroid
• Approximate center points in dense point sets
• scientific article; zbMATH DE number 1526594 (Why is no real title available?)
• Multidimensional agreement in Byzantine systems
• Computing a Segment Center for a Planar Point Set
• Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
• Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions
• COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON
• The complexity of hyperplane depth in the plane
• Approximate centerpoints with proofs
• A simple linear algorithm for computing rectilinear 3-centers
• Computational aspects of the colorful Carathéodory theorem
• Intersecting convex sets by rays
• Extending the centerpoint theorem to multiple points
• Computing a Center-Transversal Line
• Small weak epsilon-nets
• scientific article; zbMATH DE number 4213496 (Why is no real title available?)
• Algorithms for bivariate zonoid depth
• On strong centerpoints
• Packing plane spanning trees into a point set
• Construction of some computational algorithms on finite sets of points in the plane
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• Small strong epsilon nets
• Balanced line separators of unit disk graphs
• Centerpoints and Tverberg's technique
• Algorithms for center and Tverberg points
• Approximating Tverberg points in linear time for any fixed dimension
• Gathering in the plane of location-aware robots in the presence of spies
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Optimal algorithms for geometric centers and depth

This page was built for publication: Computing a centerpoint of a finite planar set of points in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338958)