A Characterization Theorem and An Algorithm for A Convex Hull Problem

Details A Characterization Theorem and An Algorithm for A Convex Hull Problem A Characterization Theorem and An Algorithm for A Convex Hull Problem

2012-04-09

arxiv.org/abs/1204.1873v1

Computer Science

Computational Geometry

15 pages, 8 figures, submitted

Scientific paper

Given a set $S= \{v_1, ..., v_n\} \subset \mathbb{R} ^m$ and a point $p \in \mathbb{R} ^m$, we wish to test if $p \in {\rm Conv}(S)$, the convex hull of $S$. This is a fundamental problem in computational geometry and linear programming. First, we prove: $p \in {\rm Conv}(S)$ if and only if for each $p' \in {\rm Conv}(S) - \{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 {\rm Conv}(S)$ such that either $d(p', p) \leq \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 ${\rm Conv}(S)$. We also show how to solve linear programming via this approximation algorithm and give a corresponding complexity analysis.

Affiliated with

Also associated with

No associations

Rating

A Characterization Theorem and An Algorithm for A Convex Hull Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Characterization Theorem and An Algorithm for A Convex Hull Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Characterization Theorem and An Algorithm for A Convex Hull Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649466