### DIMACS Theoretical Computer Science Seminar

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.

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html