... this page is part of the Web Site of George North ...

George North, ,

Homework Assignment # 2

due Friday, September 25, 1995

by: George North

439-68-5643

Computational Geometry

CSCI 6640

Fall 1995

Dr. N. Adla A. DePano

Homework Assignment # 2

** (Exercise No. 3 on p. 75 of O'Rourke's text)**

**1. ** ** ** **Min supporting line ** ** (Modayur 1991). Design an algorithm to find a line L that **

**a. has all the points of a given set to one side,**

**b. minimizes the sum of the perpendicular distances of the points to L.**

**Assume a hull algorithm is available.**

Exists an algorithm that computes the convex hull ( **H ** ) of a set of points ( **S) ** , returning an order (counter clockwise) list of points ( **h ** ) on the hull.

**Algorithm ** : Minimum supporting line - **L ** **min**

For i = 1 to h-1 (points on hull **H ** less 1)

Make line **L ** **i ** passing through points **i ** and **i+1 ** (a supporting line of **S ** )

For j = 1 to s (points in **S ** )

Sum perpendicular distance from **S ** **j ** to **L ** **i ** (each point in **S ** to line **L ** **i ** )

Remember **L ** **min ** (the line with minimum sum of perpendicular distances) ** (Exercise No. 6 on p. 75 of O'Rourke's text)**

**2. ** **Minimum area, convex. ** ** Prove characterization 9 of Section 3.1: the minimum area convex polygon enclosing a set of points is the convex hull of the points.**

Characterization 9: The convex hull of a set of points **S ** in the plane is the enclosing convex polygon P with smallest area.

Let **H ** **(S) ** be the convex hull of **S ** .

Characterization 8: the convex hull of a set of points **S ** in the plane is the smallest convex polygon **P ** that encloses **S ** (the convex hull is a convex polygon).

From Characterization 8, we know ...

1. **H ** **(S) ** is a convex polygon.

2. **H ** **(S) ** is the smallest convex polygon that encloses **S ** .

3. Using **k ** , apoint exterior to S, other convex polygons **P ** **m ** **(S) ** can be constructed that contain S.

4. **H ** **(S) ** is smaller than any **P ** **m ** **(S) ** , because **P ** **m ** **(S) ** would contain at least one more triangle than **H ** **(S) ** making its area larger than **H ** **(S) ** .

5. The area of **H ** **(S) ** is smaller than the area of any **P ** **m ** **(S) ** . **** **

6. **H ** **(S) ** is the enclosing convex polygon with smallest area.

**** ** If **h ** is the number of points on **H ** **(S) ** , exactly **h-2 ** triangles can be constructed by connecting any one point to all other points. The area of **H ** **(S) ** is the sum of the areas of these triangles. The area of any polygon **P ** **m ** **(S) ** can be calculated in a similar manner. Since every **P ** **m ** **(S) ** is composed of at least one point exterior to S, then the area of any **P ** **m ** **(S) ** will be larger that the area of **H ** **(S) ** . **3. In reference to No. 2 above, can we use the concept of perimeter as well, ** **i.e. ** **, convex hull being the polygon containing the given set of points with the smallest perimeter?**

Yes. At least two edges of any **P ** **m ** **(S) ** will be longer than the similar edges of **H ** **(S) ** . **H ** **(S) ** is the enclosing convex polygon of **S ** with the smallest perimeter.

** **

** (Exercise No. 7 on p. 75 of O'Rourke's text)**

**4. Minimum area, non convex [easy]. Show by explicit example that the minimum area polygon (perhaps non convex) enclosing a set of points might not be the convex hull of the points.**

Given identical sets of points, it is clearly possible that the area of the Convex Hull is not the minimal area of all enclosing polygons

** **

** (Exercise No. 1 on p. 80 of O'Rourke's text)**

**5. ** **Best case? ** ** Find the best case for the gift wrapping algorithm (Algorithm 3.3): sets of n points such that the algorithm's asymptotic time complexity is as small as possible as a function of n. What is the time complexity?**

The time complexity of the "gift wrap algorithm" is ** O(n * h) ** , where n is the total number of points and h is the number of points on the hull. If **n ** = **h ** , complexity is **O(n ** **2 ** **) ** , but h may be as small as **3 ** which will give best case of **3n ** or **O(n) ** .

** **

** ** ** (Exercise No. 3 on p. 111 of O'Rourke's text)**

**6. ** **Diameter and width. ** ** Define the diameter of a set of points p 0 , p 1 , ... to be the largest distance between any two points in the set: max ** **i ** **,j ** ** ** | **p ** **i ** **-p ** **j ** | **.**

**a. Prove that the diameter of a set is achieved by two hull vertices. (by contradiction)**

**b. A ** **line of support ** ** to a set is a line L that touches the hull and has all points on or to one side of ** **L ** ** . Prove that the diameter of a set is the same as the maximum distance between parallel lines of support for the set.**

**c. Two points ** **a ** ** and ** **b ** ** are called antipodal if the admit parallel lines of support: there are parallel lines of support through ** **a ** ** and ** **b ** **. Develop an algorithm for enumerating (listing) all antipodal pairs of a set of points in two dimensions. It helps to view the lines of support as jaws of a caliper. An algorithm can be based on the idea of rotation the caliper around the set.**

**d. Define the ** **width ** ** as the minimum distance between parallel lines of support. Develop an algorithm for computing the width of a set of points in two dimensions.**

6 a. Prove that the diameter of a set is achieved by two hull vertices.

1. Assume that set **S ** of points **p 0 , p 1 , ... ** has a convex hull of set **H ** points **h 0 , h 1 , ... ** . Assume that points **i, ** **j ** is ** max ** **i,j ** ** ** | **p ** **i ** **-p ** **j ** |, the largest distance between any two points in set **S ** , and assume that point **i ** or point **j ** or both are **NOT ** points on the hull (elements of **H ** ).

2. Point **i ** is NOT on the hull implies that there is a point **g, ** on the hull which forms an angle Q to which **i ** is interior. This means that another line can be formed from point **j ** to point **g ** with length equal to | **p ** **g ** **-p ** **j ** | that is greater than | **p ** **i ** **-p ** **j ** |. | **p ** **i ** **-p ** **j ** | is **NOT ** the largest distance between any two points in set **S ** . This can be shown for a line between any two points when at least one point is not on the hull.

3. Therefore, points **i, ** **j ** is ** max ** **i,j ** ** ** | **p ** **i ** **-p ** **j ** |, only if **i ** and **j ** are both points in set **H ** , points on the hull of **S ** . 6 b. A line of support to a set is a line **L ** that touches the hull and has all points on or to one side of **L ** . Prove that the diameter of a set is the same as the maximum distance between parallel lines of support for the set.

1. Points **a ** and **b ** are points in **S ** .

2. | **a-b ** | is greater than any other | **p ** **i ** **-p ** **j ** | in **S ** .

3. In question a) above, it was shown that points **a ** and **b ** are on the hull of **S ** .

4. A line drawn through **a ** and perpendicular to line **ab ** is parallel to a line drawn through **b ** and perpendicular to line **ab ** . Both of these lines are lines of support to **S ** .

5. The distance between these lines of support is | **a-b ** |, which is also the diameter of **S ** .

6 c. Two points **a ** and **b ** are called antipodal if they admit parallel lines of support: there are parallel lines of support through **a ** and **b ** . Develop an algorithm for enumerating (listing) all antipodal pairs of a set of points in two dimensions. It helps to view the lines of support as jaws of a caliper. An algorithm can be based on the idea of rotation the caliper around the set.

** ** ** ** ** **

Exists an ordered set of (at least 3) points **H ** that is the convex hull of **S ** , **h ** is the number on points in **H ** in counter clockwise order.

**Algorithm ** : Antipodal pairs

next p = 3

for i = 1 to h * outer loop executes h times

Line **L ** **i ** is a line of support containing the two points **i ** and **i+1 **

j = next p * next point on hull to check for a parallel line of support

loop * inner loop will execute maximum 2h times

make line **P ** **j ** is parallel to line **L ** **i ** passing through point **j **

if (line **P ** **j ** is a line of support at point **j ** ) then

* P j is a line of support if it does NOT pass on or within convex angle at point j

Line **L ** **i ** and line **Pj ** are parallel lines of support

SAVE points ( **i ** , **j ** ) and ( **i+1, j ** ) as an Antipodal pairs

exit loop

endif

j = j+1

end loop

next p = j

* t erminates because every point on hull has at least one parallel line of support

end loop

* algorithm will report some duplicate Antipodal pairs

**Complexity is O(h), not including finding hull of S. ** 6 d. Define the width as the minimum distance between parallel lines of support. Develop an algorithm for computing the width of a set of points in two dimensions.

Algorithm in 6c above can be used to obtain the minimum supporting line

**Algorithm ** : Width of convex polygon

W min = "some max value"

next p = 3

for i = 1 to h * outer loop executes h times

Line **L ** **i ** is a line of support containing the two points **i ** and **i+1 **

j = next p * next point on hull to check for a parallel line of support

loop * inner loop will execute maximum 2h times

make line **P ** **j ** is parallel to line **L ** **i ** passing through point **j **

if (line **P ** **j ** is a line of support at point j) then

Line **L ** **i ** and line **Pj ** are parallel lines of support

calculate **W ** **j ** , length of a line between and perpendicular to **L ** **i ** and **P ** **j **

if W min > W j then W min = W j * possible width of hull *

exit loop

endif

j = j+1

end loop

* t erminates because every point on hull has at least one parallel line of support

next p = j

end loop

W min = width of hull
*Original file name: HW2.rtf*

*This file was converted with TextToHTML - (c) Logic n.v.*