Separating bichromatic point sets in the plane by restricted orientation convex hulls
share
We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and 𝒪 be a set of k ≥ 2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of 𝒪 for which the 𝒪-convex hull of R contains no points of B. For k=2 orthogonal lines we have the rectilinear convex hull. In optimal O(n log n) time and O(n) space, n = | R | + | B |, we compute the set of rotation angles such that, after simultaneously rotating the lines of 𝒪 around the origin in the same direction, the rectilinear convex hull of R contains no points of B. We generalize this result to the case where 𝒪 is formed by k ≥ 2 lines with arbitrary orientations. In the counter-clockwise circular order of the lines of 𝒪, let α_i be the angle required to clockwise rotate the ith line so it coincides with its successor. We solve the problem in this case in O(1/Θ· N log N) time and O(1/Θ· N) space, where Θ = min{α_1,…,α_k } and N=max{k,| R | + | B |}. We finally consider the case in which 𝒪 is formed by k=2 lines, one of the lines is fixed, and the second line rotates by an angle that goes from 0 to π. We show that this last case can also be solved in optimal O(nlog n) time and O(n) space, where n = | R | + | B |.
READ FULL TEXT