## Homework # 1

 Instructor: Scot Drysdale June 24, 1996

### Homework 1

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.