Re: convex hull

From: Robin Chapman (rjc_at_ivorynospamtower.freeserve.co.uk)
Date: 02/09/05 

Date: Wed, 09 Feb 2005 19:24:33 +0000

dumb_founded wrote:

> If we describe formally the convex hull of a set S as the set that, for
> all y1, y2 member S, (alpha)*y1+(1-alpha)*y2 is a member of the convex
> hull, then will the convex hull, defined in this manner, of S be convex
> necessarily? If not, why not?

You are considering all convex combinations of TWO elements of S.
What if S is the three-element set consiting of the vertices of a triangle?
The two-element convex combinations of S form the perimeter of this
triangle, but the concex hull contains the interior of the triangle too.

A theorem of Caratheodory asserts that is S is a subset of R^n then
the convex hull of S is the set of (n+1)-element convex combinations of
elements of S. 

-- 
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
  "Elegance is an algorithm"
    Iain M. Banks, _The Algebraist_

Relevant Pages

  • Re: the smallest circle that can enclosed a convex hull
    ... The square of the radius is rho /4 - rho is to be maximize. ... compute the maximal in-circle of the polygonal convex hull of a set of points in the plane ... % Now think of it as a set of slack variables, ...
    (comp.soft-sys.matlab)
  • Re: find polygon
    ... perimeter of convex hull but would have some notches that intruded ... In most cases the perimiter of the convex hull isn't a triangle, ... the convex hull and doesn't have any straight edges, ...
    (comp.programming)
  • Another Difficult Combinatorial Geometry Problem
    ... in the plane is decomposable into a union of 3 or fewer convex sets. ... local non-convexity lie in the kernel of the set and in the planar, ... planar 3-convex sets. ... convex hull is a triangle or pentagon are relatively straightforward ...
    (sci.math.research)
  • Generalized convex perimeter of an n-d object
    ... One could define a "convex perimeter" of any bounded set of points S ... in the plane as p_2= the perimeter of the convex hull of S. ... Note that this generalized convex perimeter is a sort of dual to what ...
    (sci.math)
  • Re: Finding closest Triangle to a point
    ... a convex mesh is such that all its polygons are contained in the boundary of the convex hull formed by the vertices of the mesh. ... This also simplifies the evaluation of the potential function to a simple distance calculation between points. ... the answer to the question "which is the closest triangle to a point?" ...
    (comp.graphics.algorithms)