Separating Bichromatic Point Sets by Minimal Triangles with a Fixed Angle
Zahra Moslehi, Alireza Bagheri · International Journal of Foundations of Computer Science · 2017
Given a set P of red points and a set Q of blue points in the plane, of total size n, we investigate the problem of finding triangles with a given angle [Formula: see text] that (a) contain all points of Q, (b) avoid all points of P, and (c) are minimal, i.e. their three sides are tangent to the convex hull of Q. Such triangles are called minimal separating [Formula: see text]-triangles. We give an algorithm for reporting all combinatorially different minimal separating [Formula: see text]-triangles in [Formula: see text] time.