:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » »
 




  2.2 Circle event



Circle event happens when a parabolic arc shrinks to a point and disappears from the parabolic front (Figure 5). Let be the disappearing arc and and are two neighboring arcs before disappears. These arcs are then defined by three different points pi , pj and pk . At the moment when disappears, all three arcs pass through a common point q (Figure 5). The distance between q and the scanning line is the same as the distance from q to all three points pi , pj and pk. These three points define a circle, with its center at point q which represents the Voronoi point. The lowest point of this circle touches the scanning line and represents the circle event.

Figure 5: Parabolic arc disappears from the parabolic front

It is possible that the circle event is tried to be destroyed by some other event ("false event" or "false alarm"). Such events must be destroyed and removed from the data structure. As will be explained later, the detection of the false alarms is trivial.