Re: Convex Hull of Points on a Straight Line

O(n) time algorithm is trivial. For a set of n points in 2D
4 points x_min, x_max, y_min and y_max are always
on the convex hull. (x_min : point with the smallest
x coordinate....) All these points can be determined
in O(n) time.

For degenerate 2D problem i.e., the 1D problem
the convex hull will be determined by (x_min and
x_max) or by (y_min and y_max).

Thanks.

--- Pinaki

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



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

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: convex hull implementation in 2D
    ... CGAL also adresses the robustness issues mentioned ... Is there a paper that compares different convex hull algorithms ... fastest convex hull algorithm for point sets < 100 points. ... algorithm) and get speed (no floating-point arithmetic), ...
    (comp.graphics.algorithms)
  • Re: smallest slab enclosing n points
    ... > slab thickness. ... > to compute the convex hull of the data points. ... > computation of distance between vertex and facet. ... would contain such an algorithm. ...
    (comp.theory)
  • 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: smallest slab enclosing n points
    ... >> to compute the convex hull of the data points. ... Every floating-point algorithm in high dimensions suffers ... The distance is max-min. ...
    (comp.theory)
  • Re: smallest disk covering a set of points
    ... > Flight Physics ... >> boundary points of that convex hull. ... >> ConvHull is clearly can be done by simple divide and conquer method, ... >> worst case time Ocan be achived but the algorithm will be ...
    (comp.programming)