Back to Research & Publication
By developing relevant lemmas and theorems, this paper investigates the Steiner Tree Problem (STP) that concerns four points forming a convex quadrilateral. Creating an original recursive algorithm that has much better runtime performance than existing algorithms, this project views the STP from a completely new mathematical perspective and gives solutions of better accuracy and runtime complexity in four-point situations. The paper was inspired by a real-life problem: what is the most optimal placement of roads that connect four cities in Tibet, which achieves minimum costs? By using graph theory, the paper extracts and models this problem into a mathematical problem of determining the minimum total distance involving four different points in a plane. Specifically, the research question is hence formed as "how to solve the Steiner Tree problem in quadrilaterals using recursive algorithms?β. With the Fermat Point as the fundamental theorem in triangle case, this paper logically establishes various lemmas and theorems to investigate and generalize the Euclidean Steiner Tree problem from triangles, rectangles to arbitrary convex quadrilaterals. After reducing the numerous situation to two-point case, this project successfully proposes and proves an original recursive algorithm based on mathematical induction to determine the exact locations of the two points in arbitrary convex quadrilateral case by infinite manipulation of finding Fermat Points. After proving the validity of the two points found via the original recursive algorithm using the technique of proof by contradiction, this paper provides a Python implementation of the original recursive algorithm and examines the runtime complexity further in detail.
Modern society stresses on economization for industry activities. There are countless situations which need to be optimized. For instance, Tibet is one of the least developed provinces in China and much money was spent on building infrastructures there. In figure 1, Nagqu, Lhasa, Nyingchi and Shannan are four main cities in Tibet and goods is difficult to be transferred among the cities since only few roads connecting the cities and there is even no road between Nagqu and Nyingchi. Chinese government is building new roads there to facilitate the transportation among the cities.
Instantly, several possible βoptimalβ arrangements appear (Figure 2). Is it simply
connecting these four cities to form a quadrilateral? Is it that there is a certain point π
somewhere served as a road junction connecting four cities? Or some other ways of connecting?
With all these wondering and possibilities, the real-life problem is converted into a mathematical problem of finding the minimum sum of distance in various situations. The Fermat point The Fermat point of a triangle is a point that the total distance from the point to the triangleβs three vertices is minimized.
Figure 3 is the construction of the Fermat point of βπ΄π΅πΆ, where triangles π¨π¬πͺ , πͺππ© and π¨π«π© are equilateral. Point π, the intersection of π¨π , πͺπ« and π©π¬ , is the Fermat point
of βπ΄π΅πΆ.
However, the Fermat points and the intersections might not be applicable for n-side polygons. Thus, through thorough researching, the Steiner Tree Problem (STP) is found to address these problems.
The Euclidean Steiner Tree Problem A certain type of problem that aims to find a set of points in a geometric network π = (π, πΈ), so that βeβE|e| is minimized (π indicates the vertices set, πΈ indicates the edges set and |π| represents the Euclidean length (The distance between two points is the length of the path connecting them4) of edge π β πΈ).
Steiner Points have three properties: no two edges can join at a point with an angle smaller than 120Β°; a Steiner Tree has no crossing edges; each Steiner point in the Tree is of degree of exactly three.
n figure 47, the three red points are Steiner points which satisfy the three properties mentioned above.
With the definition and properties of the Steiner Tree Problem, this paper proceeds to explore methods to solve Steiner Tree Problem in general.
Based on previous real-life problem and the background information, this paper aims to investigate the Steiner Tree Problem concerning three points and four points forming a convex quadrilateral in a plane. In other words, the paper came up with the research question that
How to solve the Steiner Tree problem in convex quadrilaterals using efficient recursive algorithms?
To determine the locations for Steiner points, many articles about computer programming predict the positions, a non-deterministic polynomial-time hard problem (NP-Hard), by different algorithms like Primβs algorithm and Kruskalβs algorithm. could efficiently find the minimum spanning tree given vertices and edge weights. However, those algorithms are not able to determine the location of two extra Steiner points β they are only famous for finding the minimum spanning tree (MST) given vertices and edge weights. So brute force is necessary for those algorithms to find the locations of extra Steiner points, which makes the overall runtime extremely inefficient. Besides, the current methods are just very accurate approximations. A pure mathematical proof is needed to provide an alternate way to create a new algorithm or improve the existing algorithms which could predict the exact locations for Steiner points in a more efficient way, which adopts a different method from topology used in some published articles.
The real-life problem can be modelled into a simple finite graph πΊ = (π, πΈ) including π = {v1,v2,v3,β¦,vn}, the set of vertices representing different cities or additional new road junctions, and πΈ = {e1,e2,e3,β¦,em}, the set of edges denoting various potential roads to be constructed between two vertices (cities or road junctions). With graph theory, other concepts of path, circuit and tree could also be introduced to systemize and simplify the real-life problems.
Using the real-life problem as an example,
The three figures above illustrate how a Tree is modelled from the leftmost figure which shows the four cities forming a quadrilateral. The simple graph could be modelled in to a tree πΊ consisting four vertices (cities) v1,v2,v3,v4, and five edges (roads) e1,e2,e3,e4,e5 that the simple graph πΊ has no simple circuit.
To make the goal clear, π is defined based on the modelling via graph theory.
Definition 1 I define π as the sum of lengths of all the edges in a tree in a simple graph G.
(i.e. π = |e1|+|e2|+β―+|en| for a tree consisting π edges.)
Before introducing the original proof for the quadrilateral case, here is the simplified proof for the triangle case based on existing methods. Understanding the concept of this section will serve as a basic result and help in the original proof later in rectangular and convex quadrilateral cases.
Theorem 1 In any given triangle π΄π΅πΆ, S is minimized when the point inside triangle is
its Fermat point.
This is proved in appendices by geometric construction, vectors, sine rule and partial differential equations.
Hence, as in figure 6, the Steiner point π for a triangle whose three interior angles are less or equal to 120Β° is located inside the triangle which satisfy that
β BPC=β APC=β BPA=120β
which is the triangleβs Fermat point.
Based on the triangle solution, this paper will now extend the analysis to the quadrilateral case. Applying the triangle method on arbitrary quadrilateral, it becomes extremely difficult since too many variables will appear in the partial differential equations, which is unsolvable. Thus, a geometric manipulation might be adopted here to simplify and further investigate the rectangle case, starting with Lemma 1 concerning the number of points inside the triangle.
Lemma 1 For the case of rectangles, the minimum value of π is obtained when there are two points inside the rectangle.
Proof The intersection of the two diagonals is the point that minimizes π.
In figure 7, applying Triangle Inequality Theorem,
AEβ²+CEβ²>AC
BEβ²+DEβ²>BD
Therefore,
To further extend the earlier result from rectangles to convex quadrilateral, the rectangle method is applied in a more general case β convex quadrilateral case. However, as quadrilaterals have arbitrary sides and angles, the rectangular strategy is not applicable anymore. Thus, this paper will use the idea of continuous optimization and provide an original proof here, employing various techniques such as recursive algorithms (page 18-20), mathematical induction (page 21), concept of limits and proof by contradiction (page 25-28), which is not in existing literature review.
The overview of the proof is listed below:
β 1. Reducing all the possible scenarios to the two-point case.
β 2. Using recursive algorithm and Mathematical Induction to prove that exact Steiner points can be obtained.
β 3. Using limits, to establish that the two Steiner points found will generate the minimum total distance (S).
β 4. Use proof by contradiction to show that no other more optimal points can be found.
Lemma 4
For a convex quadrilateral, Smin is obtained when there are two points inside the quadrilateral.
Proof
Given only one point inside the convex quadrilateral, the intersection of the two diagonals will be the point that minimizes π.
In figure 18 above, applying Triangle Inequality Theorem ,
AEβ²+CEβ²>AC
BEβ²+DEβ²>BD
Thus,
BE+AEβ²+CEβ²+DEβ²>BE+AE+CE+DE
Hence, for any convex quadrilateral with one point inside, the intersection of twodiagonals will be the point that creates the minimum value for S.
If more than one point are in quadrilateral ABCD (figure19), without losing generality, it can be assumed that β BEC < 90Β° <β AEB. Since both β BEC and β AED are smaller than 120Β°, Fermat points P2 and P1 could always be found for both ΞAED and ΞBEC so that
BP1+CP1+P1E<BE+CEandAP2+DP2+EP2<AE+DE.
Notice P1E and P2 do not need to be collinear, if not, connecting P2 do not need to be collinear, if not, connecting P1 and P2, P1E + P2E > P1P2 always holds in ΞP1EP2.
For three or more points in the convex quadrilateral (figure 20), one of the points that is extra can always be spotted and the values of S would decrease by eliminating the point(P2 here).
Hence, for any S of one-point cases and three-or-more-point cases, a smaller value of S will always exist using two points in the given convex quadrilateral.
Given that only two-point cases are considered, this paper creates an original recursive algorithm to gradually reduce S. For quadrilateral ABCD:
Lemma 5En,Fan,Fbn can always be found for all n β N and β AEnB β CEnD β€ 120Β°
Proposition:
En,Fan,Fbn can always be found for all n β N and β AEnB β CEnD β€ 120Β°
The Basis:
Given the position of E0 assuming β AEnB β CEnD β€ 120Β° without losing generality, Fa1,Fb1 can always be found since ΞAE0B,ΞCE0D exist.
The Inductive Step:
Assume Ek exists and β AEkB,β CEkD β€ 120Β° for some k β N.
Fak+1,Fbk+1 exist and are Fermat points of triangles whose largest angles are no bigger than 120Β°, so β AFak+1B, β CFbk+1D = 120Β°.
For a point Ek+1 on Fak+1'
β AEk+1B β€ β AFak+1B = 120Β°
β CEk+1D β€ β CFbk+1D = 120Β°
By mathematical induction, En Fan and Fbn could always be found and the lemma is proben.
Lemma 5 proves that Fermat points with angles bigger than 120Β° are not involved in this algorithm. Thus, all discussions below only concern Fermat points with 120Β° angles.
This algorithm creates a monotonically decreasing sequence of the value of S after each manipulation of generating a new pair of Fermat points.
Definition 2 Let Fa0, Fb0 be two arbitrary points in a convex quadrilateral ABCD. Fan, Fbn are the Fermat points of ΞABEn-1 ΞCDEn-1 respectively for n β N where En is a point on Fan. {Sn} forms a sequence where Sn = AFan + BFan + CFbn + DFbn + FanFbn.
Lemma 6 {Sn} is a monotonically decreasing sequence.
Proof Consider Fan-1,Fbn-1 in ABCD below. For any point En-1 on Fan-1Fbn-1 such that β AEn-1B, β CEn-1D β€ 120Β°, construct ΞABEn-1 and ΞCDEn-1. Two Fermat points Fan,Fbn of the two new triangles are found.
To prove that S reduces after each recursion, what is needed to be proven is Sn β€ Sn-1 holds for all positive integer value of n.
In figure 29, Sn is the sum of lengths of red edges and Sn-1 is the sum of lengths of the green edges.En-1 is a random point on Fan-1Fbn-1 and Fan and Fbn are the Fermat points of ΞABEn-1 and ΞCDEn-1 respectively.
By Triangle inequality,
FanFbn β€ FanEn-1 + FbnEn-1
Applying the property of Fermat point of ΞABEn-1
AFan + BFan + FanEn-1 < AFan-1 + BFan-1 + Fan-1En-1
Applying the property of Fermat point of ΞCDEn-1
CFbn + DFbn + FbnEn-1 < CFbn-1 + DFbn-1 + Fbn-1En-1
Summing up both sides of the three inequalities above,
FanFbn + AFan + BFan + FanEn-1 + CFbn + DFbn + FbnEn-1 < FanEn-1 + FbnEn-1 AFan-1 + BFan-1 + Fan-1En-1 + CFbn-1 + DFbn-1 + FbnEn-1
Since
,
Thus
holds for all
. And the equity is obtained only when the two points
and
are exactly the same points as
and
. Thus,
is a monotonically decreasing sequence.
Lemma 7
converges to a finite value.
Proof
Since
and
since the sum of lengths of five segments could not be a non-positive value
for
.
If
represents an ordered set. It will have the
least upper bound if, whenever a subset
(
is nonempty) is bounded above, then in
,
has a least upper bound. Then the
supremum of
,
, can denote the least upper bound of
.
[1]
If
represents an ordered set and it has the
least upper bound property. If there is a subset
(
is nonempty) that is bounded below, then in
,
has a greatest lower bound. Then the
infimum of
,
, can denote the greatest lower bound of
.
[2]
So based on theorem 3, since
and
,
serves as the lower bound for the real set
. Therefore, there exists
.
Besides, by applying the second lemma of the monotone convergence theorem, which states that
βIf a sequence of real numbers is decreasing and bounded below, then its infimum is the limit.β [3]
Since
for
, the sequence
is a decreasing sequence and since it has infimum as proved by the
completeness of real number. Thus, by the monotone convergence theorem,
.
Theorem 4
.
Proof
Let
be the set of all possible values of
for a quadrilateral
as defined above (i.e. the set for all possible values of
generated by all possible locations of the two points inside the
quadrilateral). Clearly, infinitesimal shifting of the points leads to
infinitesimal change in value, so the set will have its upper bound
(maximum value)
and its lower bound (minimum value)
. Therefore,
is hence bounded by these two values,
.
It is known that
since the values of
generated from the recursion are only some possible values in all
possibilities. Thus,
.
Then the recursive algorithm could be proven to be valid if the value it
converges to is the same as the minimum value in all possibilities, which
is
. This is proved by contradiction in the following session.
if limnββSnβ Smin inf{Sn}>inf{S} so inf{Sn}β{S}. This means a two-point set {W,X} corresponding to inf{Sn} can always be found. Let Smin correspond to {Y,Z}. As inf{Sn} = inf{Sn}=limnββSn, for any point E on ray WX(no matter inside ABCD or outside ABCD), Fermat points of β³AEB,β³CED are still W,X. Otherwise the algorithm produces a smaller S, which contradicts. As Fermat point is the three 120 Β°, for any point F on line WX but not on the segment (Figure 30), the Fermat point on the other side of the segment still preserves.
Similarly, for Smin Y,Z preseves for triangles formed by any point on YZ and one of them preserves for a point on the line but not segment.
Line WX,YZ cannot be parallel as all angles on each Fermat point must be 120Β°. Similarly, the four points must be distinct. If they intersect at G, without losing generality, let ΞAGB be the triangle of which the Fermat point preserves. Then each set contributes one Fermat points in ΞAGB that are distinct as in figure 31. Uniqueness of Fermat points leads to contradiction. Thus, inf{Sn} = inf{Sn} and limnββSn=Smin. It is thus proven that the proposed algorithm can find positions of the two Steiner points in a convex quadrilateral.
With the idea of Finding Fermat points recursively, the following Python implementation provides an algorithm which receives coordinates of four points as input and returns output as coordinates of the two Steiner Points as well as the number of recursive calls made for the purpose of runtime analysis. (Code below generated in planetB)
Existing algorithms are mainly βbrute forceβ algorithms based on Primβs algorithm and Kruskalβs algorithm. Undoubtedly, these two algorithms are efficient in finding Minimum Spanning Trees but their runtime complexity in solving STP is still extremely high because the problem involves extra points (Steiner Points) other than existing vertices. This fact makes the STP a NP-Hard problem. However, the recursive algorithm has a much better runtime performance in four-point convex situations.
Input coordinates: (0,50), (0,0), (100,0), (100,50)
Output coordinates of Steiner Points: (14.4337,24.9999), (85.5662,24.9999)
Table of Accuracy versus number of recursion counts:
Input coordinates: (-60,0), (-10,-20), (60,0), (10,20)
Output coordinates of Steiner Points: (-12.1254, -12.3527),(12.1254,12.3526)
Table of Accuracy versus number of recursion counts:
Input coordinates: (20,50), (0,0), (100,0), (90,50)
Output coordinates of Steiner Points: (25.4496,39.3555), (36.5372)
Table of Accuracy versus number of recursion counts:
Input coordinates: A(20,60), B(-80,20), C(0,-60), D(100, 30)
Output coordinates of Steiner Points: (11.4814,36.3966),(27.8023,17.0601)
Table of Accuracy versus number of recursion counts:
Due to the constrains of computer (its smallest division limit), the test continues up to a certain level of accuracy (mostly up to Β±10-15). However, these data are sufficient to justify the runtime complexity of the recursive algorithm. It is very difficult to give the overall runtime of recursive algorithm in "Big O" or "Big 0" notation because the input is always the coordinates of the four points, and quantifying the "complexity" of a geometric shape is extremely difficult. Besides, as a recursive algorithm, it will not computationally reach the exact solution using computer (although the theoretical correctness of this algorithm is proven mathematically in previous section). However, the relationship between the accuracy and the number of recursive calls exhibits a very convincing pattern that this recursive algorithms performs much better than any other algorithms using "brute force". The relationship between the improvement on accuracy (adopts 1/Accuracy for convenience) and the number of recursive calls of the previous four tests is presented below.
Due to the constrains of computer (its smallest division limit), the test continues up to a certain level of accuracy (mostly up to Β± 10β15). However, these data are sufficient to justify the runtime complexity of the recursive algorithm. It is very difficult to give the overall runtime of recursive algorithm in "Big O" or "Big ΞΈ" notation because the input is always the coordinates of the four points, and quantifying the "complexity" of a geometry shape is extremely difficult. Besides, as a recursive algorithm, it will not reach the exact solution using computer (although it will definitely be proven by mathematics in previous sections). However, the relationship between the accuracy and the number of recursive calls exhibits a very convincing pattern that this recursive algorithms performs much better than any other algorithms using "brute force". The relationship between the improvement on accuracy (adopts 1/Accuracy for convenience) and the number of recursive calls of the previous four tests is presented below.
For both rectangle and parallelogram cases, the algorithm terminates after its first call, meaning that only one recursive call is needed to find the most optimal solution for all rectangles and parallelogram cases. Therefore, the runtime complexity is ΞΈ(1).
For a trapezium test, the recursive algorithm takes only 9 calls to reach the Β± 0.1 accuracy, which indicates that the recursive algorithm is also very efficient in reaching an solution that is relatively accurate. Furthermore, as the accuracy improves 10 times, the number of recursive calls only increases linearly . This implies that as accuracy increases exponentially, the runtime complexity increases only linearly, which is much more efficient than existing STP algorithms. Note: for visualization purpose, runtime growth = number of recursive calls x 1011
Test results for random convex quadrilateral is very similar to the case of trapezium. The data also show that the recursive algorithm converges very fast. The difference in the slope of Line Of Best Fit is most likely due to the randomness of the shape. Note: for visualization purpose, runtime growth = number of recursive calls x 1012
Now the real-life problem mentioned in introduction could be completely solved using the recursive algorithm proven in previous section.
By applying the recursive algorithm, the intersection of two diagonals, E0 could be found.
Then, the recursive algorithm could be applied and infinite pairs of Fermat points could be determined and the two points after first manipulation are found as SD and SE in figure 37. In real-life application, it is not necessary for the construction company to determine the exact Steiner points since 1β will not cause a huge increase in total distance. Thus, it could be assumed that the optimal situation is achieved if the six angles around two junctions are 120βΒ±1β.
The construction of Fermat point in figure 38 is referenced from C. Kimberling.
From the measurement in figure 3918, all six angles are within the range of 120β Β± 1β, the assumed optimal case is achieved after one manipulation and the actual construction suggestion is shown below.
Since MN is 50 km, the five roads needed to be built are shown in blue in figure 41,
Finding the minimal distance to connect multiple points has numerous applications. This problem is related to the Steiner Tree Problem and modelled using graph theory. Generally, the solution would involve finding a point set within the convex hull of the given set of vertices, and connect the vertices to the closest points in the point set and between the points in that point set. For triangle case, the solution is to connect the Fermat point to three vertices. The case of quadrilateral is the focus of this project. The rectangle case is first investigated. It is proven that when the optimal connection is made, there are two points within the rectangle. The positions of the two points are then proven to be on the longer segment of symmetry of the rectangle. It is then proven that the three angles on each of the two points within the rectangle must be 120β. This enables us to find the two-point point set given any rectangle. For an arbitrary convex quadrilateral, the two-point criterion is proven too. An original recursive algorithm is proposed to create a sequence of two-point point sets. The existence of such point set in each step of the algorithm is proven inductively, and the sequence of the total distance is proven to be monotonically decreasing and converges to the minimal possible total distance. Finally, the python implementation provides an exact algorithm that could directly solve all four-point problems. Further analysis over runtime complexity assures that the original recursive algorithm has much better performance than existing algorithms: as accuracy improves exponentially, there is only a linear increase in runtime for this recursive algorithm.
[1] M. Brazil, R. L. Graham, D. A. Thomas and M. Zachariasen, "On the History of the Euclidean Steiner Tree Problem".
[2] C. Donghui, D. D. Zhu, H. X. Dong, G. H. Lin, L. Wang and G. Xue, "Approximations for Steiner tree with minimum number of Steiner points," Theoretical Computer Science, vol. 262, pp. 83-99, 23 March 2000.
[3] G. Soothill, "The Euclidean Steiner Problem," Durham, 2010.
[4] F. Hwang, D. Richards and P.Winter, The Steiner Tree Problem, Elsevier Science Publishers, 1992, pp. 1-353.
[5] Hajia and Mowaffaq, "An Advanced Calculus Approach to Finding the Fermat Point," Mathematics Magazine, p. 29.
[6] E. Abbena, S. Salamon and A. Gray, Modern Differential Geometry of Curves and Surfaces with Mathematica, Chapman and Hall/CRC; 3 edition, 2006, p. 1016.
[7] T. H. Cormen, Introduction to Algorithms, Illustrated ed., MIT Press, 2009, pp. 634-651.
[8] K. M. Koh, F. M. Dong and E. G. Tay, Introduction to Graph Theory: H3 Mathematics, Illustrated ed., World Scientific, 2007, pp. 1-15.
[9] R. Diestel, "Graph Theory," in Graduate Texts in Mathematics, 3rd ed., vol. 173, Springer-Verlag, 2005, pp. 6-9.
[10] "The Fermat Point and Generalizations," Spot. IM Ltd., 17 October 2015. [Online]. Available: http://www.cut-the-knot.org/Generalization/fermat_point.shtml#. [Accessed 6 March 2016].
[11] M. Hazewinkel, Ed., The Encyclopedia of Mathematics, Springer, 2001.
[12] "WolframMathWorld," Mathematica Technology, 1999-2006. [Online]. Available: http://mathworld.wolfram.com/GraphCycle.html. [Accessed 6 March 2016].
[13] R. N. Aufmann and R. D. Nation, Algebra and Trigonometry, 8, illustrated ed., Cengage Learning, 2014, pp. 601-603.
[14] J. Herman, R. Kucera and J. Simsa, Equations and Inequalities: Elementary Problems and Theorems in Algebra and Number Theory, illustrated ed., Springer Science & Business Media, 2012, pp. 151- 153.
[15] W. C. Bauldry, Introduction to Real Analysis: An Educational Approach, John Wiley & Sons, 2011, pp. 47-48.
[16] J. Yeh, Real Analysis: Theory of Measure and Integration, World Scientific, 2006, pp. 14-17.
[17] C. Kimberling, Geometry in Action: A Discovery Approach Using the Geometer's Sketchpad, illustrated ed., Springer Science & Business Media, 2003, p. 15.
[18] J. Weng, "Variational approach and Steiner minimal trees on four points," Discrete Mathematics, vol. 132, no. 1-3, pp. 349-362, 11 November 1992.
Unless mentioned, all figures in this paper were drawn using Geometerβs Sketchpad.
In ΞABC below, P is a random given point in the triangle. If there are more than one point in the triangle and S is minimized, the point P' is taken as the second point.
Thus, S would be reduced if paths PP' and P'C are replaced by PC. Therefore, given point P, any additional point other than Pwouldincreasethevalueof\textit{S}sincetherewillalwaysbeacaseofonepointwhichachievesasmaller\textit{S}$ compared to multiple points.
In any given triangle ABC, S is minimized when the point inside triangle is its Fermat point.
If an arbitrary triangle ABC as the figure shown, as what is proved in the earlier section, the Steiner point of any triangle should be found inside the triangle. Establishing a coordinate system, take P as a random point with coordinates (x, y) while points A, B, and C have their coordinates (xA,yA),(xB,yB,(xC,yC) .
After substituting in the coordinates of segments PA, PB and PC, the expression
for s could be obtained as followed via the Pythagoras Theorem,
S=β(xβxA)2+(yβyA)2+β(xβxB)2+(yβyB)2+β(xβxC)2+(yβyC)2
By taking its partial derivatives with regard to x and y, and take their minimum value,
Ξ΄SΞ΄x=xβxAβ(xβxA)2+(yβyA)2+xβxBβ(xβxB)2+(yβyB)2+xβxCβ(xβxC)2+(yβyC)2=0
Ξ΄SΞ΄x=yβyAβ(xβxA)2+(yβyA)2+yβyBβ(xβxB)2+(yβyB)2+yβyCβ(xβxC)2+(yβyC)2=0
According to the figure,
xβxAPA+xβxBPB+xβxc=0
yβyAPA+yβyBPB+yβyc=0
Transfer these two equations to dot product in vector forms,
Since
Ξ±β
Ξ΄=Ξ²β
Ξ΄=0
Hence Ξ΄ is perpendicular to both Ξ± and Ξ², and thus parallel to the cross product between
Ξ± and Ξ²,
Ξ±ΓΞ²=(xβxAxβxBxβxC)Γ(yβyAyβyByβyC)=(|xβxByβyBxβxCyβyC|β|xβxAyβyAxβxCyβyC||xβxAyβyAxβxByβyB|)
Thus, as shown in Figure 46,
|xβxAyβyAxβxCyβyC|=(xβxA)(yβyC)β(xβxC)(yβyA)=β2ΓArea ofβ³APC
Similarly,
|xβxAyβyAxβxCyβyC|=(xβxA)(yβyC)β(xβxC)(yβyB)
Thus,
(xβxA)(yβyC)β(xβxC)(yβyB)=AFΓGH+EFΓDE
Besides,
Areaofβ³APC=12AEΓAHβGPΓGHβ12(AFΓAG)β12(PDΓPI)
Areaofβ³APC=12AEΓAHβGPΓGHβ12(AFΓAG)β12(PDΓPI)
2ΓAreaofβ³APC=(AF+EF)(AG+GH)β2ΓGPΓGHβ(AFΓAG)β(EFΓDC)=AFΓGH+EFΓAGβ2ΓAFΓGH=EFΓAGβAFΓGH=(xcβx)(yAβy)β(xβxA)(yβyC)
|xβxAyβyAxβxCyβyC|=(xβxA)(yβyC)β(xβxC)(yβyA)=β2ΓArea ofβ³APC
For the same reason and method,
|xβxAyβyAxβxByβyB|=(xβxA)(yβyB)β(yβyA)(xβxB)=β2ΓArea ofβ³PAB
Therefore, convert the previous cross product to the following expression,
Ξ±ΓΞ²=(xβxAxβxBxβxC)Γ(yβyAyβyByβyC)=(|xβxByβyBxβxCyβyC|β|xβxAyβyAxβxCyβyC||xβxAyβyAxβxByβyB|)=(β2ΓArea ofβ³PBCβ2ΓArea ofβ³PACβ2ΓArea ofβ³PAB)
Since
2ΓArea ofβ³PBC=2Γ12Γ|βPB|Γ|βPC|Γsinβ BPC
2ΓArea ofβ³PAC=2Γ12Γ|βPA|Γ|βPC|Γsinβ APC
2ΓArea ofβ³PAB=2Γ12Γ|βPB|Γ|βPA|Γsinβ BPA
Thus,
Ξ±ΓΞ²=(β|βPB|Γ|βPC|Γsinβ BPCβ|βPA|Γ|βPC|Γsinβ APCβ|βPB|Γ|βPA|Γsinβ BPA)
Since Ξ΄ is is parallel to Ξ±ΓΞ², so for a certain value of Ξ³, there will be
Ξ΄=(1|βPA|1|βPB|1|βPC|)=Ξ³(|βPB|Γ|βPC|Γsinβ BPC|βPA|Γ|βPC|Γsinβ APC|βPB|Γ|βPA|Γsinβ BPA)
which is equivalent to
1|βPA|=Ξ³Γ|βPB|Γ|βPC|Γsinβ BPC
1|βPB|=Ξ³Γ|βPA|Γ|βPC|Γsinβ APC
1|βPC|=Ξ³Γ|βPB|Γ|βPA|Γsinβ BPA
Hence, as shown in figure 48, with Ξ³ is a constant value,
1Ξ³Γ|βPA|Γ|βPB|Γ|βPC|=sinβ BPC=sinβ APC=sinβ BPA
Since
β BPC<180β
β APC<180β
β BPA<180β
And at point P,
β BPC=β APC=β BPA=360β
Therefore,
β BPC=β APC=β BPA=120β
Spring 2018
Ziming Xue and Rigel
Navigation