The recursive algorithm of the 4th Section of the chapter "Computational Geometry"
employs a trick of presorting, in which we maintain two arrays X and Y of the input
points P sorted on coordinate x and y, respectively. The algorithm starts with sorting
all the input points in Q in time O(n log n). Assuming that a subset P Q of input
points together with arrays X and Y are given, set P is partitioned into PL and PR and
the corresponding arrays XL, XR, YL, and YR are all obtained in time O(/P/). To see
this, observe that the median xm of x-coordinates of the points in P is the x coordinate
of the point in the middle of X. To obtain YL and YR, scan array Y and move a point
(x,y) with x < xm to YL and a point (x, y) with x xm to YR.
Consider a modi cation of the recursive algorithm in which presorting is not applied.
Instead, we sort in each recursive call, applying an algorithm sorting by comparisons.
Each time a given subset P needs to be partitioned into PL and PR, the points in P
are sorted on the x-coordinate. In the "combine" part, the set of points in the vertical
strip of width 2ä is sorted on the y-coordinates.
Find a tight asymptotic estimate on the running time of this algorithm as a function
of the size n of the input set Q.
Hints: Find a recurrence for the running time. It is dierent from the recurrence
T(n) = 2T(n=2) + O(n) describing the version with presorting. Solve the recurrence.
To this end, you might apply the approach used to prove the \master theorem" of
Chapter "Divide-and-Conquer."
Diameter of a convex polygon.
There is given a convex polygon P, represented as a sequence of consecutive points
(p0, p1,........ pn-1)
in the sense that the polygon P consists of segments pi, pi+1, where the addition of
subscripts is modulo n.
1) Give an efficient algorithm to nd a pair of points in P of the maximum distance
from each other.
A readable description of the underlying idea of the algorithm in words, possibly illus-
trated with simple drawings, will be better than a tight pseudocode.
2) Argue why the algorithm is correct.
The correctness of the algorithm is to rely on the convexity of the polygon. Point in
your correctness argument where you resort to convexity.
3) Estimate the running time of the algorithm.
The goal is to design an algorithm of the asymptotically optimal running time.
Please contact me at
msjaiswal[at]gmail[dot]com
for solutions.
Price 10$
To find a pair of points in a convex polygon P of the maximum distance from each other, you can use the following algorithm:
1) Initialize two variables, maxDistance and maxPoints, to keep track of the maximum distance found so far and the corresponding pair of points.
2) Iterate through each pair of consecutive points in the polygon, denoted as (p[i], p[i+1]). Calculate the distance between these two points using the Euclidean distance formula: dist = sqrt((p[i].x - p[i+1].x)^2 + (p[i].y - p[i+1].y)^2).
3) If the calculated distance is greater than the current maxDistance, update maxDistance to the new distance and set maxPoints to the pair of points (p[i], p[i+1]).
4) After iterating through all pairs of points, check the distance between the first and last point in the polygon, denoted as (p[n-1], p[0]). If this distance is greater than maxDistance, update maxDistance and maxPoints accordingly.
5) At the end of the algorithm, maxPoints will contain the pair of points in the polygon with the maximum distance between them.
Here's an illustration of the algorithm:
```
maxDistance = 0
maxPoints = ()
for i = 0 to n-2 do:
dist = sqrt((p[i].x - p[i+1].x)^2 + (p[i].y - p[i+1].y)^2)
if dist > maxDistance:
maxDistance = dist
maxPoints = (p[i], p[i+1])
dist = sqrt((p[n-1].x - p[0].x)^2 + (p[n-1].y - p[0].y)^2)
if dist > maxDistance:
maxDistance = dist
maxPoints = (p[n-1], p[0])
return maxPoints
```
To argue the correctness of the algorithm, we rely on the convexity of the polygon. The key observation is that any point inside the polygon must be closer to at least one of the edges than the outermost points of the polygon.
Since a convex polygon has no concave angles, the maximum distance between any pair of points must occur between two consecutive points on the boundary of the polygon. Therefore, by considering all pairs of consecutive points, we are guaranteed to find the maximum distance within the convex polygon.
The running time of the algorithm is O(n), where n is the number of points in the polygon. This is because we iterate through all pairs of consecutive points in the polygon to calculate the distances and update the maximum distance and points. The time complexity remains linear regardless of the size or shape of the polygon.