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

centerpointlinear-time algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4213496
• 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

(37)

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

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)