A near-linear algorithm for the planar segment-center problem

DOI10.1007/BF02711511zbMath0868.68112OpenAlexW3136790239MaRDI QIDQ1816414

Micha Sharir, Alon Efrat

Publication date: 26 November 1996

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02711511

zbMATH Keywords

segment-center problem

Mathematics Subject Classification ID

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

Related Items (5)

Continuous location of dimensional structures. ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ Simple wriggling is hard unless you are a fat hippo ⋮ On 0-1 matrices and small excluded submatrices ⋮ Unnamed Item

Cites Work

• Geometric pattern matching under Euclidean motion
• Diameter, width, closest line pair, and parametric searching
• Geometric complexity of some location problems
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• A Turán-type theorem on chords of a convex polygon
• Computing the smallest \(k\)-enclosing circle and related problems
• Extremal polygon containment problems
• Almost tight upper bounds for lower envelopes in higher dimensions
• The maximum number of unit distances in a convex \(n\)-gon
• On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
• The overlay of lower envelopes and its applications
• COMPUTING SHORTEST TRANSVERSALS OF SETS
• Computing a Segment Center for a Planar Point Set
• Optimal Point Location in a Monotone Subdivision
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Extremal Problem on Sparse 0-1 Matrices
• Parallel Transitive Closure and Point Location in Planar Structures
• 1-Segment Center Problems
• Parallelism in Comparison Problems
• Static and dynamic algorithms for k-point clustering problems
• Unnamed Item

This page was built for publication: A near-linear algorithm for the planar segment-center problem