Instructor: Scot Drysdale | June 24, 1996 |

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