SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS

DOI10.1142/S0218195906001902zbMath1093.68042MaRDI QIDQ5291404

Carlos Seara, Joseph S. B. Mitchell, Ferran Hurtado, Esther M. Arkin, Steven S. Skiena

Publication date: 10 May 2006

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

lower boundsseparationmaximum gap

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Separability of imprecise points, Separability by two lines and by nearly straight polygonal chains, PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS, Processing an Offline Insertion-Query Sequence with Applications, On the 2-Center Problem Under Convex Polyhedral Distance Function, Dynamic minimum bichromatic separating circle, Separating Bichromatic Point Sets by Minimal Triangles with a Fixed Angle, The class cover problem with boxes, Minimizing the error of linear separators on linearly inseparable data, Separating bichromatic point sets in the plane by restricted orientation convex hulls, ON COMPUTING ENCLOSING ISOSCELES TRIANGLES AND RELATED PROBLEMS, SEPARABILITY OF POINT SETS BY k-LEVEL LINEAR CLASSIFICATION TREES

Cites Work

• Algorithms for weak and wide separation of sets
• Computing circular separability
• Geometric complexity of some location problems
• Minimum polygonal separation
• Obtaining lower bounds using artificial components
• Finding minimal convex nested polygons
• Implicit convex polygons
• Separability by two lines and by nearly straight polygonal chains
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Separating objects in the plane by wedges and strips