Re: Convex Hull of Points on a Straight Line

Babua wrote:
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

OK.

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).

How does the "So the 1D problem can be solved in O(n) time" follow from
your convex combination statement? I don't get it.

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.

Interesting. In the lower-bound proof for computing the convex hull,
the points are mapped on one of the 90 degree arcs of a circle.

.

Relevant Pages

  • Re: Convex Hull of Points on a Straight Line
    ... Babua wrote: ... then any convex hull will be a line segment. ... of any two points within that segment also belongs to that segment. ... I ask because there is a version of Graham's algorithm in my discrete ...
    (comp.theory)
  • Re: Convex Hull of Points on a Straight Line
    ... This is a degenerate 2D problem. ... then any convex hull will be a line segment. ... of any two points within that segment also belongs to that segment. ... I ask because there is a version of Graham's algorithm in my discrete ...
    (comp.theory)
  • Re: Convex Hull of Points on a Straight Line
    ... Otime algorithm is trivial. ... on the convex hull. ... eKo1 wrote: ... of any two points within that segment also belongs to that segment. ...
    (comp.theory)