KGP13J - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Jingbo Shang

DIFFICULTY:

Hard

PREREQUISITES:

Voronoi Diagram

PROBLEM:

Given N points, find the area of the maximum empty circumcircle of an acute-angled triangle (3 corners are from N points).

EXPLANATION:

First of all, I think this problem is a classical problem and then I search online. I find that it is called Largest Empty Circle. From wikipedia, we know that it is related to Voronoi Diagram and solvable in O(NlogN).

To calculate the Voronoi Diagram (VD) in O(NlogN) time, we can use Fortune’s algorithm (These N points are equivalent to the sites in Fortune’s algorithm). After that, let’s store the O(N) vertices of VD in a list V. For each vertex v, store also the following info:

  1. sites nearest to v (these sites lie on the largest empty circle centered at v).
  2. distance dv of the sites nearest to v.

All these info are obtained and stored during the circle event corresponding to v.

Then, we sort V in non-increasing order of dv and check these vertices in order. For a given vertex v, consider every three nearest sites (only a small constant number of nearest sites it may have) of v to decide whether it forms an acute-angled triangle. If yes, return the area of the circle centered at v and of radius dv. Otherwise, take the next vertex into consideration. This procedure also needs O(NlogN) time.

2

Can this problem be solved by Delaunay triangulation as well? Going by the definition of the method Delaunay, we can compute the circumcircle area for every triangle formed and take the maximum of it.