شبه مثلث

شبه المثلث

[عدل]
Pseudotriangles

شبه المثلث Pseudotriangle في هندسة المستوى الإقليدي، (أو المثلث الزائف) هو المجموعة الفرعية المتصلة ببساطة من المستوى، وتقع بين أي ثلاث مجموعات محدبة متبادلة الظل. وهو تشابك تمتد حوافه عند كل رأس بزاوية أقل من π.

استخدمت الكلمتين شبه المثلث "pseudotriangle" وتثليث المستوى "pseudotriangulation" في الرياضيات لفترة طويلة.[1] يُستخدم تثليث المستوى للكشف عن التصادمات بين الأجسام المتحركة.[2] ولرسم الرسم البياني الديناميكي وتحويل الأشكال.[3] وتبدو شبه المثلثات المدببة في نظرية الصلابة بمثابة أمثلة على الرسوم البيانية المستوية ذات الحد الأدنى من الصلابة.[4] وفي طرق تحديد أماكن الحراس فيما يتعلق بنظرية معرض الفنون.[5]

أوضح كلُ من Pocchiola and Vegter (1996) أن شبه المثلث يكون منطقة متصلة من المستوى يحدها ثلاثة منحنيات محدبة ناعمة المماس عند نقاط نهايتها. ولكن فيما بعد وُضِعَ تعريف أوسع ينطبق بشكل عام على المضلعات وكذلك على المناطق التي تحدها منحنيات ناعمة، والتي تسمح بزوايا غير صفرية عند الرؤوس الثلاثة. في هذا التعريف الأوسع، فإن شبه المثلث هو منطقة متصلة ببساطة من المستوى، لها ثلاثة رؤوس محدبة. يجب أن تكون منحنيات الحدود الثلاثة التي تربط هذه الرؤوس الثلاثة محدبة، بمعنى أن أي قطعة خطية تربط نقطتين على نفس منحنى الحدود يجب أن تقع بالكامل خارج أو على حدود شبه المثلث. وبالتالي، فإن شبه المثلث هو المنطقة الواقعة بين الهياكل المحدبة لهذه المنحنيات الثلاثة بشكل عام.[6] [7] [8]

وفيما يخص التطبيقات الخوارزمية، يكون من المهم بشكل خاص توصيف أشباه المثلثات من المضلعات.

المصادر

[عدل]
  1. ^ For "pseudo-triangle" see, e.g., Whitehead, J. H. C. (1961), "Manifolds with transverse fields in Euclidean space", Annals of Mathematics, 73 (1): 154–212, doi:10.2307/1970286, JSTOR 1970286, MR 0124917. On page 196 this paper refers to a "pseudo-triangle condition" in functional approximation. For "pseudo-triangulation" see, e.g., Belaga, È. G. (1976), "[Heawood vectors of pseudotriangulations]", Doklady Akademii Nauk SSSR (in Russian), 231 (1): 14–17, MR 0447029.
  2. ^ Agarwal, Pankaj K.; Basch, Julien; Guibas, Leonidas J.; Hershberger, John; Zhang, Li (2002), "Deformable free-space tilings for kinetic collision detection", International Journal of Robotics Research, 21 (3): 179–197,
  3. ^ Streinu, Ileana (2000), "A combinatorial approach to planar non-colliding robot arm motion planning", Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 443–453, doi:10.1109/SFCS.2000.892132, S2CID 9420124.
  4. ^ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications, 31 (1–2): 31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802, S2CID 38637747.
  5. ^ Speckmann, Bettina; Tóth, Csaba D. (2005), "Allocating vertex π-Guards in simple polygons via pseudo-triangulations", Discrete and Computational Geometry, 33 (2): 345–364, doi:10.1007/s00454-004-1091-9, MR 2121300.
  6. ^ Pocchiola, Michel; Vegter, Gert (1996a), "The visibility complex", International Journal of Computational Geometry and Applications, 6 (3): 297–308, doi:10.1142/S0218195996000204, archived from the original on 2006-12-03. Preliminary version in Ninth ACM Symp. Computational Geometry (1993) 328–337.
  7. ^ Pocchiola, Michel; Vegter, Gert (1996b), "Topologically sweeping visibility complexes via pseudotriangulations", Discrete and Computational Geometry, 16 (4): 419–453, doi:10.1007/BF02712876, MR 1414964.
  8. ^ Pocchiola, Michel; Vegter, Gert (1996c), "Pseudo-triangulations: theory and applications", Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 291–300, doi:10.1145/237218.237398, S2CID 15948239.