1) In class I claimed that the convex hull could be used to find a "best line" through
a set S of n points in the plane, where a "best line" is defined to be one that minimizes
the distance between the line and the farthest point from the line. I did not say how to accomplish this. Explain how to do this.
a) What is the minimum number of points that must achieve the maximum distance? Describe
how these points must lie in relation to the best line and to one another.
b) Describe how to use the convex hull to quickly find all such sets of points. How
long will your algorithm take, as a function of h, the number of points on the convex
hull?
2) In class we talked about methods of computing the convex hull, and claimed that
any algorithm to compute the convex hull must take W(n log n) time. However, it is possible to determine whether a single given point
p in S is an extreme point (on the convex hull) in q(n) time. Describe an algorithm to do this.
Outline of answers:
1a) There must be two points on one side of the best line and one point on the other
side of the best line that all achieve the maximum distance from the best line.
Furthermore, the projection of the single point must lie between the projections
of the other two. If all the points achieving the minimum distance lie on one side of the
best line, then translating the line in the direction of the points will reduce the
distance, contradicting the assumption that it was the best line. If the projections
are not as described, then rotating the line reduces the distance to the farthest points.
1b) A rotating calipers approach will allow us to find for each edge of the convex
hull the point farthest away from it on the opposite side of the hull. If there
are h edges on the CH(S), then finding all such edge-point pairs will take q(h) time. Given the edge-point pair of minimum distance the best line passes equidistant
from the edge and the point. (In the case of parallel edges, it may pass equidistant
from two edges instead.)
2) The basic idea is to determine if the point p lies in or on a triangle of points
in S. Trying all triangles would take far too long. Instead we take a second point
x in S and construct the ray xp. We consider this ray to be both sides of a 0 wedge
centered at p. We then consider in turn each other point in S. If the next y point
lies within the current wedge, we throw it away. If not, make the ray py the side
of an expanded wedge, replacing the side that is closest (in terms of angle) to py.
If the wedge ever grows to be at least as large as 180 then p cannot lie on the convex
hull. (It must lie in or on a triangle formed by the new point and the points defining
the rays that bounded the wedge before the new point was added.) If not, then p
is an extreme point, because both sides of the wedge can be extended to form lines of
support for S.
Mailto: dimacs-www@dimacs.rutgers.edu
Last modified: October 3, 1996