CSE355/AMS345 Theory Project
留学生作业代写代做 Suppose we are given a subdivision of the plane into n convex regions and we suspect that this is a Voronoi diagram.
Solve three out of the fifive problems below. A report on these problems is due by December 16th, 2018. Notice that these problems are generally harder than our homework problems.
1.Give an O(n log n) algorithm for the convex hull of a set of n circles (possibly intersecting and possibly with difffferent radii). 留学生作业代写代做
2.Suppose we are given a subdivision of the plane into n convex regions and we suspect that this is a Voronoi diagram. Develop an algorithm to fifind n sites whose Voronoi diagram is exactly the given subdivision, if such a set exists.
3.Take S as n axis-parallel rectangles in the plane. Design a data structure such that we can answer queries quickly: given a query rectangle [xa, xb]×[ya, yb], report all rectangles of S that are completely contained in the query rectangle. The goal is to have storage of O(n log3 n) and query time O(log3 +k).
4.Consider a Voronoi diagram, in which each site pi is a circle of radius ri and the distance from a point q to this circle is 留学生作业代写代做
|q − pi | 2 − ri 2 .
Defifine the Voronoi diagram to be a decomposition such that all points in the same cell has the same (weighted) sites (or circles) to be the closest.
Show that 1) the Voronoi diagram for such circles has all Voronoi edges to be straight line segments. 2) Provide an algorithm of O(n log n) to compute such a Voronoi diagram.
5.A point x is called a centerpoint of a set of n points P if every halfplane that includes x also includes at least n/3 points. Prove that a centerpoint always exists for any point set. And show an algrothm to compute a centerpoint.
