Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)

DOI10.1016/j.tcs.2015.11.048zbMath1333.68252OpenAlexW2191739325MaRDI QIDQ906384

Subhas C. Nandy, Sasanka Roy, Binay K. 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

dualityarrangementcenterpointprune-and-searchspace-efficient algorithm

Mathematics Subject Classification ID

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

Related Items

Constant work-space algorithms for facility location problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-time trade-offs for stack-based algorithms
• Selection from read-only memory and sorting with minimum data movement
• Computing a ham-sandwich cut in two dimensions
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Computing a centerpoint of a finite planar set of points in linear time
• Improved bounds for planar \(k\)-sets and related problems
• Approximations and optimal geometric divide-and-conquer
• Finding median in read-only memory on integer input
• Comparison-based time-space lower bounds for selection
• Partitioning with two lines in the plane
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms
• Selection from Read-Only Memory with Limited Workspace
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Selection and Sorting in the “Restore” Model
• Finding the convex hull of a simple polygon