employs a trick ofpresorting, in whichwe maintain two arrays Xand Yof the input
ID: 3615073 • Letter: E
Question
employs a trick ofpresorting, in whichwe maintain two arrays Xand Yof the input
points P sorted on coordinatex andy, respectively. Thealgorithm starts with sorting
points together witharrays X and Y are given, set Pis partitioned into PL and PR and
the corresponding arraysXL,XR,YL, andYR are allobtained in time O(/P/). To see
this, observe that themedian xm of x-coordinates of the points in P is the x coordinate
of the point in the middleof X. Toobtain YL and YR, scan array Yand move a point
Consider a modi cation of therecursive algorithm in which presorting is not applied.
Instead, we sort in eachrecursive call, applying an algorithm sorting bycomparisons.
Each time a given subsetP needs to bepartitioned into PLand PR, the points inP
are sorted on thex-coordinate. In the"combine" part, the set of points in the vertical
strip of width2 is sorted onthe y-coordinates.
Find a tight asymptotic estimateon the running time of this algorithm as a function
of the size n of the input setQ.
Hints: Find a recurrence for the running time. It is dierent fromthe recurrence
T(n) =2T(n=2)+ O(n) describing the version withpresorting. Solve the recurrence.
To this end, you might applythe approach used to prove the master theorem" of
Chapter"Divide-and-Conquer."
Explanation / Answer
Dear,
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.