Re: Convex Hull of Points on a Straight Line

If we take two points (x1,y1) and (x2,y2) then by a convex
combination of these two points we mean any point of the
following form:

[kx1+(1-k)x2, ky1+(1-k)y2] for 0<=k<=1

In this context I would just like to add a point that in
the lower bound proof where sorting is reduced to convex
hull problem to avoid the problem of colineraity the data
x for sorting is mapped to the point (x,x^2) on a parabola
and not to (x,x) on a line for the 2D convex hull problem.

Thanks.

---- Pinaki

====================================================================
eKo1 wrote:
What do you mean by "convex combination?" Would you provide an example?


Babua wrote:
This is a degenerate 2D problem. If you consider it as a 1D problem
then any convex hull will be a line segment. Any convex combination
of any two points within that segment also belongs to that segment.
So the 1D problem can be solved in O(n) time unlike the 2D problem
that is lower bounded by \omega(nlogn).

Thanks.

--- Pinaki

==================================================================


eKo1 wrote:
Let L be a straight line on the cartesian plane. Pick a finite set of
points S on that line. What is the convex hull of S?

From my understanding of hull points, the convex hull is the two points
farthest away from each other in S. Is this true?

I ask because there is a version of Graham's algorithm in my discrete
mathematics book that does not consider the case when there are two
points whose segments with the first hull point have the same angle
with respect to the horizontal. I guess this version of the algorithm
is flawed in that respect.

.

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: convex hull
    ... > hull, then will the convex hull, defined in this manner, of S be convex ... What if S is the three-element set consiting of the vertices of a triangle? ...
    (sci.math)