|
2 pm - 3 pm, Seminar Hall Algorithm for Plane Matchings in Multipartite Geometric Graphs Subhas Nandy Indian Statistical Institute, Kolkata. 03-07-15 Abstract Let P be a set of n points in general position in the plane which is partitioned into color classes. P is said to be color-balanced if the number of points of each color is at most n/2 . Given a color-balanced point set P , a balanced cut is a line which partitions P into two color- balanced point sets, each of size at most 2n/3+1. A colored matching of P is a perfect matching in which every edge connects two points of distinct colors by a straight line segment. A plane colored matching is a colored matching which is non-crossing. We present an algorithm which computes a balanced cut for P in linear time. Consequently, we present an algorithm which computes a plane colored matching of P optimally in (n log n) time. This is a joint work with Ahmad Biniaz, Anil Maheshwari, and Michiel Smid to be appeared in WADS 2015.
|
