Re: Convex Hull of Points on a Straight Line

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: 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
    ... Otime algorithm is trivial. ... on the convex hull. ... eKo1 wrote: ... of any two points within that segment also belongs to that segment. ...
    (comp.theory)
  • Re: Convex Hull of Points on a Straight Line
    ... of any two points within that segment also belongs to that segment. ... the lower bound proof where sorting is reduced to convex ... and not to on a line for the 2D convex hull problem. ...
    (comp.theory)
  • Re: Convex Hull of Points on a Straight Line
    ... If we take two points and then by a convex ... and not to on a line for the 2D convex hull problem. ... 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: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)