3

Given n points , no three of them are collinear. i and j , 2 points are friends if the circle formed with i &j as diameter does not contain any of the other points. Give all such points in O(nlogn)

Peter
  • 2,719
  • 4
  • 25
  • 55
  • Nope , m not able to figure out nlogn algorithm for , it , infact no better then checking all points for every pair , i.e n^3 – Peter Dec 08 '12 at 20:46
  • O(n^2) is easy there. are you sore about O(nlogn) ? – ashley Dec 08 '12 at 21:22
  • come to think of it, just to enumerate the point pairs randomly takes O(n^2). what kind of output encoding are you looking at ? – ashley Dec 08 '12 at 21:31
  • all pairs of points n^2 , then checking whther other points lie in the circle n, total n^3 – Peter Dec 09 '12 at 06:58

4 Answers4

5

You are trying to compute what is known as the relative neighborhood graph in the literature. The lune determined by the two points must be empty. There is quite a bit of literature on this topic. You could start with the Wikipedia article. As user tmyklebu says, it is a subset of the Delaunay triangulation.

      Lune

Correction. I misread the conditions, as Asiri kindly explained. The relevant graph is instead the Gabriel Graph, which also has a considerable literature:

      enter image description here

Joseph O'Rourke
  • 4,346
  • 16
  • 25
  • totally unrelated, thank you for great articles and books ^_^ – George Profenza Dec 09 '12 at 03:14
  • `circle formed with i & j as diameter` I thought that meant a circle with a diameter equal to the distance between `i` and `j` (which means `i` and `j` will be on the circumference of this circle - with the mid point between `i` and `j` as the center). But the *lune* as you pointed out seems to be a different area. I am totally alien to computational geometry, trying to understand the problem. Cheers! – Asiri Rathnayake Dec 09 '12 at 10:44
1

Compute the Delaunay triangulation. If two points are friends, they must be neighbours in the Delaunay triangulation.

The converse is not true, however; you need to check each of the (linearly many) edges in the Delaunay triangulation to see whether another point lies within the circle. To do this, iterate over all of the edges. Call the ends of the current iterate u and v. The neighbours of u can be enumerated in clockwise order starting from v; let a_1 be the next neighbour of u clockwise from v and a_2 be the next neighbour of u counterclockwise from v. You only need to check that a_1 and a_2 do not lie in the circle with uv as its diameter.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57
0

I'm not very confident with this answer, please correct me if I'm wrong.

We start with the first two points, so there's only one circle. This circle can be represented by (p1, p2, c, r) where c and r are the center and the radius of the circle (they can be calculated on the fly as well).

Now we incrementally add the rest of the points while breaking / making new circles as needed.

So, at some step if we have an m number of circles, and we are attempting to introduce the point p, scan through m and see if p is inside any of the circles (can be determined efficiently given c and r). If p is inside some circle, then destroy that circle and create two new circles (with p and the two points from the circle that was destroyed).

If on the other hand p is outside all the circles, then we need to find the point which is closest to p and create a new circle. Now I'm not entirely sure how you can find the "closest point to p" efficiently, may be something like this?

Apologies if I'm totally off the track!

UPDATE: Not sure what to do if there are more than 1 "closest points to p". May be create that many new circles (?).

Community
  • 1
  • 1
Asiri Rathnayake
  • 1,138
  • 1
  • 11
  • 27
0

Plug the following into Delaunay triangulation:

Define first D(x,y) to denote the distance between points x and y.

Property-I: Given any 2 points p1 and p2, a third point p3 is on or inside the circle of which one of the diameters is the segment formed by p1 and p2 iff 

D(p1,p3)^2+D(p2,p3)^2<=D(p1,p2)^2.

This is because an angle on the circle is half the degree of the portion of the circle it is seeing and the one seeing the diameter is thus right.

So, any p1 and p2 are friends iff the point(s) (at most 2 such points) forming a triangle with it in Delaunay tiles both satisfy Property-I.

ashley
  • 1,177
  • 1
  • 14
  • 17