Separating bichromatic point sets by L-shapes

DOI10.1016/j.comgeo.2015.06.008zbMath1335.65035OpenAlexW1763890873MaRDI QIDQ904108

Mark T. de Berg, Mansoor Davoodi, Ali Mohades, Farnaz Sheikhi

Publication date: 15 January 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2015.06.008

zbMATH Keywords

algorithmseparabilitytime complexityAckermann functionoutput-sensitive algorithmbichromatic point setsL-shapeworst-case optimal algorithm

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items (6)

Geometric separability using orthogonal objects ⋮ Separability of imprecise points ⋮ Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms ⋮ Variations of largest rectangle recognition amidst a bichromatic point set ⋮ Separating bichromatic point sets in the plane by restricted orientation convex hulls ⋮ Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

Cites Work

• Unnamed Item
• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• Computing circular separability
• Minimum polygonal separation
• Maintenance of configurations in the plane
• On range searching with semialgebraic sets
• Almost tight upper bounds for vertical decompositions in four dimensions
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms
• Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations
• Separating objects in the plane by wedges and strips

This page was built for publication: Separating bichromatic point sets by L-shapes