Detecting Inclusions for O-convex hulls of Bichromatic Point Sets

EasyChair Preprint 3186

Abstract

Let O be a set of lines through the origin. Given two disjoint sets of n red and n blue points in the plane, we study the problem of maintaining the subset of blue points contained in the O-convex hull of the red point set while we rotate O around the origin. We describe efficient algorithms to solve the problem when O contains two lines. We consider the case where we simultaneously rotate both lines, and the case where one line is rotated while the second one is kept fixed.

Keyphrases: bichromatic point sets, inclusion detection, restricted orientation convex hull

@booklet{EasyChair:3186,
  author    = {Carlos Alegrı́a and David Orden and Carlos Seara and Jorge Urrutia},
  title     = {Detecting Inclusions for O-convex hulls of Bichromatic Point Sets},
  howpublished = {EasyChair Preprint 3186},
  year      = {EasyChair, 2020}}