Title: A Characterization Theorem and An Algorithm for A Convex Hull Problem
Speaker: Bahman Kalantari, Rutgers University
Date: Wednesday, April 11, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Given a set S = {v_1, ..., v_n} in the m-dimensional Euclidean space and a point p, we wish to test if p lies in Conv(S), the convex hull of S. This is a fundamental problem in computational geometry and linear programming. First, we prove: p lies in Conv(S) if and only if for each p' in Conv(S), different than p, there exists v_j in S such that the Euclidean distance inequality d(p', v_j) > d(p, v_j) holds. Next, we describe a fully polynomial time approximation scheme: given epsilon > 0 in O(mn/epsilon^2) arithmetic operations it computes p' in Conv(S) such that either d(p', p) <= epsilon*d(p,v_j) for some j, or d(p', v_i) < d(p, v_i) for all i=1, ..., n. In the latter case the hyperplane that orthogonally bisects the line pp' separates p from Conv(S). We also show how to solve linear programming via this approximation algorithm and give a corresponding complexity analysis.