मोनोटोन बहुभुज
ज्यामिति में, समतल में एक बहुभुज P को एक सीधी रेखा L के संबंध में 'मोनोटोन' कहा जाता है, यदि L के लिए ओर्थोगोनल प्रत्येक रेखा P की सीमा को अधिक से अधिक दो बार काटती है।[1]
इसी तरह, एक बहुभुज श्रृंखला C को एक सीधी रेखा L के संबंध में 'मोनोटोन' कहा जाता है, यदि प्रत्येक रेखा L के लिए ओर्थोगोनल C को अधिक से अधिक एक बार काटती है।
कई व्यावहारिक उद्देश्यों के लिए इस परिभाषा को ऐसे मामलों की अनुमति देने के लिए विस्तारित किया जा सकता है जब पी के कुछ किनारे एल के लिए ऑर्थोगोनल होते हैं, और एक साधारण बहुभुज को मोनोटोन कहा जा सकता है यदि एक रेखा खंड जो पी में दो बिंदुओं को जोड़ता है और एल के लिए ऑर्थोगोनल है, पी में पूरी तरह से स्थित है।
मोनोटोन कार्यों के लिए शब्दावली के बाद, पूर्व परिभाषा एल के संबंध में 'बहुभुज सख्ती से मोनोटोन' का वर्णन करती है।
गुण
मान लें कि एल एक्स-अक्ष | एक्स-अक्ष के साथ मेल खाता है। फिर एक मोनोटोनिक बहुभुज के बाएँ और दाएँ कोने अपनी सीमा को दो मोनोटोन बहुभुज श्रृंखलाओं में विघटित कर देते हैं, जैसे कि जब किसी श्रृंखला के शीर्षों को उनके प्राकृतिक क्रम में पार किया जा रहा हो, तो उनके एक्स-निर्देशांक एकरस रूप से बढ़ रहे हैं या घट रहे हैं। वास्तव में, इस गुण को मोनोटोन बहुभुज की परिभाषा के लिए लिया जा सकता है और यह बहुभुज को अपना नाम देता है।
एक उत्तल बहुभुज किसी भी सीधी रेखा के संबंध में मोनोटोन होता है और एक बहुभुज जो प्रत्येक सीधी रेखा के संबंध में मोनोटोन होता है वह उत्तल होता है।
एक रैखिक समय एल्गोरिदम सभी दिशाओं की रिपोर्ट करने के लिए जाना जाता है जिसमें एक दिया गया सरल बहुभुज मोनोटोन होता है।[2] एक साधारण बहुभुज को दो मोनोटोन श्रृंखलाओं (संभवतः अलग-अलग दिशाओं में एकरस) में विघटित करने के सभी तरीकों की रिपोर्ट करने के लिए सामान्यीकृत किया गया था।[3] एक मोनोटोन बहुभुज के संबंध में बहुभुज प्रश्नों में बिंदुओं का उत्तर रैखिक समय प्रीप्रोसेसिंग के बाद लघुगणकीय समय में दिया जा सकता है (बाएं और सबसे दाएं कोने खोजने के लिए)।[1]
रैखिक समय में एक मोनोटोन बहुभुज आसानी से बहुभुज त्रिभुज हो सकता है।[4] विमान में बिंदुओं के दिए गए सेट के लिए, एक बिटोनिक टूर एक मोनोटोन बहुभुज है जो बिंदुओं को जोड़ता है। गतिशील प्रोग्रामिंग का उपयोग करके बहुपद समय में एक निश्चित दिशा के संबंध में निर्धारित बिंदु के लिए न्यूनतम परिधि बिटोनिक टूर पाया जा सकता है।[5] यह आसानी से दिखाया गया है कि ऐसा न्यूनतम बिटोनिक दौरा एक साधारण बहुभुज है: नए दौरे की बिटोनिकिटी को संरक्षित करते हुए क्रॉसिंग किनारों की एक जोड़ी को एक छोटी गैर-क्रॉसिंग जोड़ी से बदला जा सकता है।
एक साधारण बहुभुज आसानी से बहुभुज त्रिकोणासन हो सकता है#O(n log n) समय में मोनोटोन बहुभुज का उपयोग करना। हालाँकि, चूंकि एक त्रिभुज एक मोनोटोन बहुभुज है, बहुभुज त्रिभुज वास्तव में एक बहुभुज को मोनोटोन वाले में काट रहा है, और यह O(n) समय में एक जटिल एल्गोरिथ्म के साथ सरल बहुभुजों के लिए किया जा सकता है।[6] रैखिक अपेक्षित समय के साथ एक सरल यादृच्छिक एल्गोरिथम भी जाना जाता है।[7]
बहुपद समय में एक साधारण बहुभुज को समान रूप से मोनोटोन बहुभुजों (यानी, एक ही पंक्ति के संबंध में मोनोटोन) की न्यूनतम संख्या में काटना किया जा सकता है।[8] गति योजना के संदर्भ में, दो गैर-अंतर्विभाजक मोनोटोन बहुभुज एक ही अनुवाद द्वारा अलग-अलग होते हैं (यानी, एक बहुभुज का अनुवाद मौजूद होता है जैसे कि दो अलग-अलग आधा विमानों में सीधी रेखा से अलग हो जाते हैं) और यह अलगाव रैखिक समय में पाया जा सकता है .[9]
सामान्यीकरण
स्वीप करने योग्य बहुभुज
एक बहुभुज को स्वीपेबल कहा जाता है, यदि एक सीधी रेखा को पूरे बहुभुज पर लगातार इस तरह से ले जाया जा सकता है कि किसी भी समय बहुभुज क्षेत्र के साथ इसका प्रतिच्छेदन एक उत्तल सेट है। एक मोनोटोन बहुभुज एक रेखा द्वारा स्वीप करने योग्य होता है जो स्वीप के दौरान अपना अभिविन्यास नहीं बदलता है। एक बहुभुज पूरी तरह से स्वीप करने योग्य होता है यदि उसके क्षेत्र का कोई भी भाग एक से अधिक बार स्वीप नहीं किया जाता है। द्विघात समय में दोनों प्रकार की व्यापकता को पहचाना जाता है।[10]
3डी
उच्च आयामों के लिए बहुभुज की एकरूपता का एक भी सीधा सामान्यीकरण नहीं है।
एक दृष्टिकोण में संरक्षित monotonicity विशेषता लाइन एल है। एक तीन आयामी पॉलीहेड्रॉन को दिशा एल में 'कमजोर मोनोटोनिक' कहा जाता है यदि सभी क्रॉस-सेक्शन ऑर्थोगोनल टू एल सरल बहुभुज हैं। यदि क्रॉस-सेक्शन उत्तल हैं, तो पॉलीहेड्रॉन को 'उत्तल अर्थ में कमजोर मोनोटोनिक' कहा जाता है।[9]बहुपद समय में दोनों प्रकारों को पहचाना जा सकता है।[10]
एक अन्य दृष्टिकोण में संरक्षित एक आयामी विशेषता ओर्थोगोनल दिशा है। यह तीन आयामों में बहुफलकीय भूभाग की धारणा के लिए जन्म देता है: संपत्ति के साथ एक पॉलीहेड्रल सतह जो प्रत्येक लंबवत (यानी, जेड अक्ष के समानांतर) रेखा सतह को एक बिंदु या खंड से अधिक से अधिक काटती है।
यह भी देखें
- ऑर्थोगोनल उत्तलता, पॉलीगोन के लिए जो दो परस्पर ऑर्थोगोनल दिशाओं के संबंध में एक साथ मोनोटोन हैं; निश्चित दिशाओं की किसी भी संख्या के लिए एक सामान्यीकरण भी।
- सितारे के आकार का बहुभुज, मोनोटोन बहुभुजों का एक ध्रुवीय निर्देशांक एनालॉग
संदर्भ
- ↑ 1.0 1.1 Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry – An Introduction, Springer-Verlag, ISBN 0-387-96131-3, 1st edition: ; 2nd printing, corrected and expanded, 1988: ; Russian translation, 1989
- ↑ Preparata, Franco P.; Supowit, Kenneth J. (1981), "Testing a simple polygon for monotonicity", Information Processing Letters, 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0.
- ↑ Rappaport, David; Rosenbloom, Arnold (1994), "Moldable and castable polygons", Computational Geometry, 4 (4): 219–233, doi:10.1016/0925-7721(94)90020-5.
- ↑ Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301, S2CID 33344266
- ↑ Introduction to Algorithms, 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001. Problem 15-1, p. 364.
- ↑ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
- ↑ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376
- ↑ Liu, Robin (1988), "On decomposing polygons into uniformly monotone parts", Information Processing Letters, 27 (2): 85–89, doi:10.1016/0020-0190(88)90097-X.
- ↑ 9.0 9.1 Toussaint, G. T.; El Gindy, H. A. (1984), "Separation of two monotone polygons in linear time", Robotica, 2 (4): 215–220, doi:10.1017/S0263574700008924.
- ↑ 10.0 10.1 Bose, Prosenjit; van Kreveld, Marc (2005), "Generalizing monotonicity: On recognizing special classes of polygons and polyhedra by computing nice sweeps", International Journal of Computational Geometry & Applications, 15 (6): 591–608, doi:10.1142/S0218195905001877, hdl:1874/24150.
