Exercise: prove the last proposition in this text. Assume that space is \mathcal{R}^2…
- User
Exercise: prove the last proposition in this text. Assume that space is \mathcal{R}^2
Let be a generating set ( P ), composed of the 22 generating points of a Voronoi diagram. This set is constructed as follows:
The first point is placed at the center. The other 21 points are generated around this central point. Two Voronoi regions are said to be adjacent if they share at least one common edge. Points generating regions that share no edges with the central point are not considered adjacent. Points whose regions are adjacent to those of the central point are colored distinctly. We generate a set ( Adj_P ) that contains only points adjacent to (but not including) the center point.
There are ways of ensuring that the region generated by the red dot remains unchanged despite changes to the set of black dots. In the proposed Python code, we use an “ad hoc” method, consisting in constructing the convex envelope of the blue points, then generating the black points outside this envelope.
Suppose two points ( p_i ) and ( p_r ) are fixed in a two-dimensional space. Let ( R(p_i, p_r) ) be the region containing the set of points closer to ( p_i ) than to ( p_r ), and let ( R(p_r, p_i) ) be the region containing the set of points closer to ( p_r ) than to ( p_i ). An improvement to the Python code would be to develop an algorithmic method for determining, for any point ( p_k ) in the same two-dimensional space, whether :
( R(p_k, p_i) ) is entirely contained within ( R(p_r, p_i) ), in which case the intersection between ( R(p_k, p_i) ) and ( R(p_i, p_r) ) is empty. The intersection between ( R(p_k, p_i) ) and ( R(p_i, p_r) ) is not empty. It seems intuitive that any point not lying on the straight line through ( p_i ) and ( p_r ) satisfies the second condition, if we consider two-dimensional space to be infinite.
- Assistant
To prove the last proposition, we need to show that for any point ( p_k ) not lying on the straight line through ( p_i ) and ( p_r ) in a two-dimensional space ( \mathbb{R}^2 ), the intersection between ( R(p_k, p_i) ) and ( R(p_i, p_r) ) is not empty.
Definitions:
- Let ( p_i ) and ( p_r ) be two fixed distinct points in ( \mathbb{R}^2 ).
- Let ( p_k ) be any point in ( \mathbb{R}^2 ) not lying on the line through ( p_i ) and ( p_r ).
- ( R(a, b) ) is the region containing all points closer to ( a ) than to ( b ). Mathematically, ( R(a, b) = { x \in \mathbb{R}^2 : | x - a | \leq | x - b | } ).
Goal:
Prove that ( R(p_k, p_i) \cap R(p_i, p_r) \neq \emptyset ).
Proof:
-
Without Loss of Generality (WLOG), Fix ( p_i ) at the Origin:
We can place ( p_i ) at the origin ( (0, 0) ) for simplicity. Let ( p_r ) be at point ( (x_r, y_r) ), and ( p_k ) be at point ( (x_k, y_k) ).
-
Bisector Between ( p_i ) and ( p_r ):
The set of points equidistant from ( p_i ) and ( p_r ) forms the perpendicular bisector of the segment ( p_i p_r ). The equation of this bisector is:
[ | x - p_i | = | x - p_r | ]
Since ( p_i ) is at the origin, this simplifies to:
[ \sqrt{x^2 + y^2} = \sqrt{(x - x_r)^2 + (y - y_r)^2} ]
Squaring both sides and simplifying, we find the equation of the bisector ( B_{i,r} ):
[ 2x x_r + 2y y_r = x_r^2 + y_r^2 ]
-
Bisector Between ( p_k ) and ( p_i ):
Similarly, the bisector between ( p_k ) and ( p_i ) is given by:
[ 2x x_k + 2y y_k = x_k^2 + y_k^2 ]
-
The Half-Planes ( R(p_i, p_r) ) and ( R(p_k, p_i) ):
- ( R(p_i, p_r) ) consists of all points ( x ) satisfying ( | x - p_i | \leq | x - p_r | ), which corresponds to one side of the bisector ( B_{i,r} ).
- ( R(p_k, p_i) ) consists of all points ( x ) satisfying ( | x - p_k | \leq | x - p_i | ), corresponding to one side of the bisector ( B_{k,i} ).
-
Intersection of the Half-Planes:
- Since ( p_k ) does not lie on the line through ( p_i ) and ( p_r ), the bisectors ( B_{i,r} ) and ( B_{k,i} ) are not parallel—they intersect at a single point.
- The half-planes ( R(p_i, p_r) ) and ( R(p_k, p_i) ) are determined by these bisectors. Because the bisectors are not parallel, the intersection of the half-planes is a convex region (specifically, a wedge-shaped region).
-
Non-Empty Intersection:
- The intersection ( R(p_k, p_i) \cap R(p_i, p_r) ) contains all points that are simultaneously closer to ( p_k ) than to ( p_i ) and closer to ( p_i ) than to ( p_r ).
- Since the half-planes intersect in a wedge and are convex, their intersection is also convex and extends infinitely in the plane.
- Therefore, unless ( p_k ) lies on the line through ( p_i ) and ( p_r ), the intersection is non-empty.
-
Colinear Exception:
- If ( p_k ) lies on the line through ( p_i ) and ( p_r ), the bisectors ( B_{i,r} ) and ( B_{k,i} ) can be parallel or even coincide, depending on the position of ( p_k ).
- If they coincide, the half-planes may or may not overlap, and their intersection could be empty.
- If they are parallel and the half-planes face opposite directions, their intersection is empty.
- This special case aligns with the proposition, which states that the intersection may be empty if ( p_k ) lies on the line through ( p_i ) and ( p_r ).
- If ( p_k ) lies on the line through ( p_i ) and ( p_r ), the bisectors ( B_{i,r} ) and ( B_{k,i} ) can be parallel or even coincide, depending on the position of ( p_k ).
Conclusion:
We have shown that for any point ( p_k ) not lying on the straight line through ( p_i ) and ( p_r ), the regions ( R(p_k, p_i) ) and ( R(p_i, p_r) ) intersect, meaning their intersection is non-empty. This confirms the last proposition.
Hence, the proposition is proven.