Saturday

December 20, 2014

December 20, 2014

Posted by **roba** on Saturday, November 14, 2009 at 4:58pm.

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.

- computers -
**Mayank**, Friday, April 22, 2011 at 2:50amPlease contact me at

msjaiswal[at]gmail[dot]com

for solutions.

Price 10$

**Answer this Question**

**Related Questions**

4th Grade Math - Arrays and an expanded algorithm: 23 x 17

graham school - how,arrays and an expanded algorithm it is a 4th grade homework

programming - 1. Write a structured algorithm that prompts the user to input two...

Computers - Problem-Solving 1. Develop an algorithm or write pseudocode to ...

programming - Consider the following input and output: INPUT: (((5 + 1) – (7 – 4...

programming - Write pseudocode to accept as input names of an unspecified number...

programming - Write pseudocode (using pascal) to accept as input names of an ...

computers - Develop an algorithm or write a pseudo-code that accepts as input ...

pseudocode programming - Develop an algorithm or write pseudocode to determine ...

Math - What the heck is recursive? recursive: repeats Going up a stairwell is a...