Computing circular separability

DOI10.1007/BF02187688zbMath0598.52008OpenAlexW2130596403MaRDI QIDQ1079817

Nimrod Megiddo, Joseph O'Rourke, S. Rao Kosaraju

Publication date: 1986

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

Full work available at URL: https://eudml.org/doc/130985

zbMATH Keywords

algorithmlinear programmingVoronoi diagramscircular separabilityspherical separability

Mathematics Subject Classification ID

Linear programming (90C05) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Related Items (24)

Geometric separability using orthogonal objects ⋮ Separability of imprecise points ⋮ Identification of points using disks ⋮ SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS ⋮ Minimum polygonal separation ⋮ The number of different digital \(N\)-discs ⋮ THE LARGEST EMPTY ANNULUS PROBLEM ⋮ On the complexity of polyhedral separability ⋮ Topological relations between separating circles ⋮ Dynamic minimum bichromatic separating circle ⋮ Separating bichromatic point sets by L-shapes ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Variations of largest rectangle recognition amidst a bichromatic point set ⋮ Separating bichromatic point sets in the plane by restricted orientation convex hulls ⋮ Digital circles, spheres and hyperspheres: from morphological models to analytical characterizations and topological properties ⋮ Separability and Tight Enclosure of Point Sets ⋮ Algorithms for weak and wide separation of sets ⋮ Separating objects in the plane by wedges and strips ⋮ Locating an obnoxious plane ⋮ COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS ⋮ Measure of circularity for parts of digital boundaries and its fast computation ⋮ On the ball spanned by balls ⋮ On Three Constrained Versions of the Digital Circular Arc Recognition Problem ⋮ FINDING THE LARGEST EMPTY DISK CONTAINING A QUERY POINT

Cites Work

• Fast detection of polyhedral intersection
• Finding extreme points in three dimensions and solving the post-office problem in the plane
• Voronoi diagrams and arrangements
• Computing largest empty circles with location constraints
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• Optimal Search in Planar Subdivisions
• Convex hulls of finite sets of points in two and three dimensions
• The complexity of linear programming

This page was built for publication: Computing circular separability