...
A key part is then to select one candidate circle out of these multiple circles. In this technique, the center of the finally selected Apollonius circle is considered as the target location. The circle selection in Apollonius is a critical part and is explained here ( https://confluence.slac.stanford.edu/display/IEPM/Circle+selection+for+Apollonius+results )
Apollonius circles are three special circles say c1,c2,c3. The set of points with a constant ratio of distances d1/d2 to two fixed points know as foci is one of the circle. c1 is unique circle passing to vertex A of triangle ABC (figure ) that maintain constant ratio of distances to other two vertices B and C. similarly c2 is passing to vertex B of triangle and maintain constant ratio of distances to other two vertices A and C . and so is the case with c3.
...
There are many ways to solve construct Apollonius circle.
- Solve three circles that are non-arbitrary i.e they are excircles of a triangle. (Figure 5)
As shown in figure 5 below every triangle have 3 ex-circles. A circle inside three circles and tangent to them is the circle of Apollonius.
- Solve three arbitrary circles. i.e at any position(except they are not nested in each other) and find Solution circles that can be at max 8 circles. and one of these eight circle is Apollonius circle. (Figure 1, Figure 2, Figure 3)
We have implemented the second case. i.e used three arbitrary circles to find solution circles.Apollonius solution One of the eight circles that is simultaneously tangent to three given circles (i.e., a circle solvingApollonius' problem for three circles).
Apollonius circles are up to eight in number that are tangent to three circles (defined above. And one of these eight circles is a Apollonius Circle (used cluster method to find that circle).
Application
In our algorithm to solve IP based Geolocation we have tried to embed this technique to find our required target. To get three circles of Apollonius we used our 3 landmarks giving minRTT after pinging the target node. This minRTT is then converted to 1 way delay which is then used to estimate the distance = RTT * alpha to get radius of the circle. In this way we get the three circles of Apollonius which are used by our algorithm to find circles that are tangent to these three circles. The resultant circles are up to eight in number or less. After getting eight or fewer circles we need to find one circle which is near our target. We have used cluster approach to find this one circle and then compared this technique with a manual method to view the performance of our cluster approach. (https://confluence.slac.stanford.edu/display/IEPM/Circle+selection+for+Apollonius+results)
...