computers
posted by roba .
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 xcoordinates 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 xcoordinate. In the "combine" part, the set of points in the vertical
strip of width 2ä is sorted on the ycoordinates.
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 "DivideandConquer."
Diameter of a convex polygon.
There is given a convex polygon P, represented as a sequence of consecutive points
(p0, p1,........ pn1)
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$
Respond to this Question
Similar Questions

geometry
1.in which geometry do lines no contain an infinite number of points? 
4th Grade Math
Arrays and an expanded algorithm: 23 x 17 
Computers
ProblemSolving 1. Develop an algorithm or write pseudocode to determine if a citizen is eligible to vote. The criteria for eligibility are that the citizen must be 18 or older and must not be a convicted felon. The algorithm must … 
graham school
how,arrays and an expanded algorithm it is a 4th grade homework 
math
A,B are two points on a given line L.L is the midpoint of the section AB. find the coordinate of point B if the coordinate of A=7 and the coordinate of L=4 
programming
1. Write a structured algorithm that prompts the user to input two numbers. The algorithm should calculate and print the sum & product of the two numbers [21/2] 
Math Statistics
The sorting algorithm known as bogosort can be described in pseudocode as: while not isSorted(input): shuffle(input) If we feed bogosort a shuffled array of length n of unique items the distribution of the number of times bogosort … 
GEOMETRY
POINTS M,N, AND O ARE 3 POINTS ON A LINE WITH COORDINATE 5, 2 SQUARE ROOT OF 5 AND 3 SQUARE ROOT OF 2 RESPECTIVELY, WHICH POINT IS BETWEEN THE OTHER TWO ? 
programming
Consider the following input and output: INPUT: (((5 + 1) – (7 – 4)) / (11 – 8)) OUTPUT: 5 1 + 7 4 – – 11 8  / 2.1. What variables do you need to consider for the input? 
pseudo code algorithm
Write a pseudo code algorithm which: • Determines the average weight of a person over a particular year. • For each month, your algorithm should input the person's weight for that month (a positive real number). Your algorithm …