employs a trick of presorting, in which we maintain two arrays X and Y of the in
ID: 3615047 • Letter: E
Question
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
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
(
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
are sorted on the
strip of width
Find a tight asymptotic estimate on the running time of this algorithm as a function
of the size
Hints:
T
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
in the sense that the polygon
subscripts is modulo
1) Give an efficient algorithm to nd a pair of points in
from each
Explanation / Answer
P denotes the set of points.
X denotes a permutation of {1, 2, ..., n} that is obtained bysorting the points according to their x-coordinates in increasingorder.
Y denotes a permutation of {1, 2, ..., n} that is obtained bysorting the points according to their y-coordinates in increasingorder.
Pre-sorts are once in the beginning of the algorithm it hasdone. The time taken for this is known to be (n lgn).
The input to the algorithm as the combination [P, X, Y ], wedivide the problem and give the sub-problems in the same manner. Wewill also assume without loss of generality that the points arenumbered as per X.
DIVIDE:
We divide the problem into roughly two equal parts by taking thepoints in the two halves as per the sorting X.
COMBINE:
Now we need to combine all this to get the results for P.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.