Chapter 33, Problem 1P

a.

Program Plan Intro

To give an algorithm that takes $O\left(n^2\right)$ timeto find the convex layers of a set havingn points.

Explanation of Solution

The technique used to compute the convex hull of set Q is known as Package wrapping technique. It was given by Jarvis march.

The total running time of the algorithm is $O\left(nh\right)$ , where h is the number of vertices of CH (Q).

And if there are K convex layers and the layer contains $l_i$ points, the total running time is

  $O\left(n{l}_1+n{l}_2+\dots \dots .+n{l}_k\right)\equiv O\left(n^2\right)$ .Since ${\displaystyle \sum _{i=1}^K{l}_i=n}$ .

b.

Program Plan Intro

To prove that the time required to compute the convex layers of set having npoints is $\Omega \left(n\log n\right)$ .

Explanation of Solution

The following is the sorting problem which can be done in linear time.

• If the numbers are given in sorted order, the convex layers can be determined in linear time.
• Suppose there is a convex layer say A with 3 points into set Q for each $A\left[k\right]:\left(0,0\right),\left(k,0\right)$ and $\left(0,A\left[k\right]\right)$ .
• Also supposeQ be withn convex layers and $Q_i$ be a triangle representation with the vertices $\left(0,0\right),\left(n+i-1,o\right)$ and $\left(0,B\left[i\right]\right)$ .
• Therefore, the corresponding sorted value can be obtained from each convex layer when they are converted.
• Since, finding convex layers can be done in lower bound. The time taken to determine convex layers will be $O\left(n\log n\right)$ and also these can be sorted in $O\left(n\log n\right)$ time.

Hence, a convex layer takes $\Omega \left(n\log n\right)$ time.