Space-efficient algorithm for computing a centerpoint of a set of points in R^2

DOI10.1016/J.TCS.2015.11.048MaRDI QIDQ906384zbMATH OpenOpenAlexFDO

Authors Subhas C. Nandy, Sasanka Roy, Binay Bhattacharya

Publication date 21 January 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.11.048

zbMATH Keywords

dualityarrangementprune-and-searchcenterpointspace-efficient algorithm

Mathematics Subject Classification ID

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

Recommendations

• Computing a centerpoint of a finite planar set of points in linear time
• Algorithms for center and Tverberg points
• scientific article; zbMATH DE number 4213496

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3541764 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximations and optimal geometric divide-and-conquer
• Comparison-based time-space lower bounds for selection
• Computing a centerpoint of a finite planar set of points in linear time
• Computing a ham-sandwich cut in two dimensions
• Finding median in read-only memory on integer input
• Finding the convex hull of a simple polygon
• Improved bounds for planar \(k\)-sets and related problems
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Partitioning with two lines in the plane
• Selection and sorting in the ``restore model
• Selection and sorting with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Selection from read-only memory with limited workspace
• Slowing down sorting networks to obtain faster sorting algorithms
• Space-time trade-offs for stack-based algorithms
• Upper bounds for time-space trade-offs in sorting and selection

Cited in

(3)

• Computing a centerpoint of a finite planar set of points in linear time
• Constant work-space algorithms for facility location problems
• Optimal algorithms for geometric centers and depth

This page was built for publication: Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)

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