मोनोटोन बहुभुज: Difference between revisions
No edit summary |
No edit summary |
||
| Line 19: | Line 19: | ||
समतल में बिंदुओं के दिए गए समूह के लिए, एक [[बिटोनिक टूर]] एक मोनोटोन बहुभुज है जो बिंदुओं को जोड़ता है। [[गतिशील प्रोग्रामिंग]] का प्रयोग करके बहुपद समय में एक निश्चित दिशा के संबंध में निर्धारित बिंदु के लिए न्यूनतम परिधि में बिटोनिक टूर पाया जा सकता है।<ref>''[[Introduction to Algorithms]]'', 2nd ed., [[Thomas H. Cormen|T. H. Cormen]], [[Charles E. Leiserson|C. E. Leiserson]], [[Ron Rivest|R. Rivest]], and [[Clifford Stein|C. Stein]], [[MIT Press]], 2001. Problem 15-1, p. 364.</ref> यह आसानी से दिखाया गया है कि ऐसा न्यूनतम बिटोनिक दौरा एक साधारण बहुभुज है: नए दौरे की बिटोनिकिटी को संरक्षित करते हुए क्रॉसिंग किनारों की एक जोड़ी को एक छोटी गैर-क्रॉसिंग जोड़ी से बदला जा सकता है। | समतल में बिंदुओं के दिए गए समूह के लिए, एक [[बिटोनिक टूर]] एक मोनोटोन बहुभुज है जो बिंदुओं को जोड़ता है। [[गतिशील प्रोग्रामिंग]] का प्रयोग करके बहुपद समय में एक निश्चित दिशा के संबंध में निर्धारित बिंदु के लिए न्यूनतम परिधि में बिटोनिक टूर पाया जा सकता है।<ref>''[[Introduction to Algorithms]]'', 2nd ed., [[Thomas H. Cormen|T. H. Cormen]], [[Charles E. Leiserson|C. E. Leiserson]], [[Ron Rivest|R. Rivest]], and [[Clifford Stein|C. Stein]], [[MIT Press]], 2001. Problem 15-1, p. 364.</ref> यह आसानी से दिखाया गया है कि ऐसा न्यूनतम बिटोनिक दौरा एक साधारण बहुभुज है: नए दौरे की बिटोनिकिटी को संरक्षित करते हुए क्रॉसिंग किनारों की एक जोड़ी को एक छोटी गैर-क्रॉसिंग जोड़ी से बदला जा सकता है। | ||
[[File:Polygon-to-monotone.png|thumb|एक बहुभुज को मोनोटोन बहुभुजों में तोड़ना]]O(n log n) समय में एक साधारण बहुभुज आसानी से | [[File:Polygon-to-monotone.png|thumb|एक बहुभुज को मोनोटोन बहुभुजों में तोड़ना]]O(n log n) समय में एक साधारण बहुभुज आसानी से मोनोटोन बहुभुजों में काटा जा सकता है। चूंकि एक त्रिभुज एक मोनोटोन बहुभुज है, बहुभुज त्रिभुज वास्तविक में एक बहुभुज को मोनोटोन वाले में काट रहा है, और यह O(n) समय में एक जटिल कलां विधि के साथ सरल बहुभुजों के लिए भी किया जा सकता है।<ref>{{citation | ||
| last=Chazelle | first=Bernard | author-link=Bernard Chazelle | | last=Chazelle | first=Bernard | author-link=Bernard Chazelle | ||
| title=Triangulating a Simple Polygon in Linear Time | | title=Triangulating a Simple Polygon in Linear Time | ||
Revision as of 07:44, 8 December 2022
ज्यामिति में, समतल में एक बहुभुज P को एक सीधी रेखा L के संबंध में 'मोनोटोन' कहा जाता है, यदि L के लिए लंबकोणीय प्रत्येक रेखा P की सीमा को अधिक से अधिक दो बार काटती है।[1]
इसी के अनुसार, एक बहुभुज श्रृंखला C को एक सीधी रेखा L के संबंध में 'मोनोटोन' कहा जाता है, यदि प्रत्येक रेखा L के लिए लंबकोणीय C को अधिक से अधिक एक बार काटती है।
कई प्रयोगात्मक उद्देश्यों के लिए इस परिभाषा को ऐसे स्थितियो की अनुमति देने के लिए विस्तारित किया जा सकता है जब p के कुछ किनारे L के लिए लंबकोणीय होते हैं, यदि एक रेखा खंड जो p में दो बिंदुओं को जोड़ता है और L के लिए लंबकोणीय है, p में पूरी तरह से स्थित है। तो एक साधारण बहुभुज को मोनोटोन कहा जा सकता है
मोनोटोन फलनो के लिए शब्दावली के बाद, पूर्व परिभाषा L के संबंध में 'बहुभुजों को सख्ती से मोनोटोन' का वर्णन करती है।
गुण
मान लें कि L X-अक्ष के संपाती है। फिर एक मोनोटोनिक बहुभुज के बाएँ और दाएँ कोने अपनी सीमा को दो मोनोटोन बहुभुज श्रृंखलाओं में विघटित कर देते हैं, जैसे कि जब किसी श्रृंखला के शीर्षों को उनके प्राकृतिक क्रम में पार किया जा रहा हो, तो उनके X-निर्देशांक एक समान रूप से बढ़ रहे होंगे या एक समान रूप से घट रहे होंगे। यथार्थ, इस गुण को मोनोटोन बहुभुज की परिभाषा के लिए लिया जा सकता है और यह बहुभुज को अपना नाम देता है।
एक उत्तल बहुभुज किसी भी सीधी रेखा के संबंध में मोनोटोन होता है और एक बहुभुज जो प्रत्येक सीधी रेखा के संबंध में मोनोटोन होता है वह उत्तल होता है।
एक रैखिक समय कलन विधि सभी दिशाओं की सूचना देने के लिए जाना जाता है जिसमें एक दिया गया सरल बहुभुज मोनोटोन होता है।[2] एक साधारण बहुभुज को दो मोनोटोन श्रृंखलाओं (संभवतः अलग-अलग दिशाओं में एकरस) में विघटित करने के सभी विधियो की सूचना देने के लिए सामान्यीकृत किया गया था।[3]
एक मोनोटोन बहुभुज के संबंध में बहुभुज प्रश्नों में बिंदुओं का उत्तर रैखिक समय पूर्वप्रक्रमण के बाद लघुगणकीय समय में दिया जा सकता है (बाएं और सबसे दाएं कोने खोजने के लिए)।[1]
एक मोनोटोन बहुभुज को रेखीय समय में आसानी से त्रिभुजित किया जा सकता है।[4]
समतल में बिंदुओं के दिए गए समूह के लिए, एक बिटोनिक टूर एक मोनोटोन बहुभुज है जो बिंदुओं को जोड़ता है। गतिशील प्रोग्रामिंग का प्रयोग करके बहुपद समय में एक निश्चित दिशा के संबंध में निर्धारित बिंदु के लिए न्यूनतम परिधि में बिटोनिक टूर पाया जा सकता है।[5] यह आसानी से दिखाया गया है कि ऐसा न्यूनतम बिटोनिक दौरा एक साधारण बहुभुज है: नए दौरे की बिटोनिकिटी को संरक्षित करते हुए क्रॉसिंग किनारों की एक जोड़ी को एक छोटी गैर-क्रॉसिंग जोड़ी से बदला जा सकता है।
O(n log n) समय में एक साधारण बहुभुज आसानी से मोनोटोन बहुभुजों में काटा जा सकता है। चूंकि एक त्रिभुज एक मोनोटोन बहुभुज है, बहुभुज त्रिभुज वास्तविक में एक बहुभुज को मोनोटोन वाले में काट रहा है, और यह O(n) समय में एक जटिल कलां विधि के साथ सरल बहुभुजों के लिए भी किया जा सकता है।[6] रैखिक अपेक्षित समय के साथ एक सरल यादृच्छिक कलां विधि भी जाना गया है।[7]
एक साधारण बहुभुज को समान रूप से मोनोटोन बहुभुजों की न्यूनतम संख्या में काटना (अर्थात्, एक ही पंक्ति के संबंध में मोनोटोन) बहुपद समय में किया जा सकता है।[8]
गति योजना के संदर्भ में, दो गैर-अंतर्विभाजक मोनोटोन बहुभुज एक ही अनुवाद द्वारा अलग-अलग होते हैं (अर्थात्, एक बहुभुज का अनुवाद उपस्थित होता है जैसे कि दो अलग-अलग आधा समतलो में सीधी रेखा से अलग हो जाते हैं) और यह पृथकत्व रैखिक समय में पाया जा सकता है .[9]
सामान्यीकरण
घुमने के योग्य बहुभुज
एक बहुभुज को व्यापक कहा जाता है,यदि एक सीधी रेखा को पूरे बहुभुज पर लगातार इस तरह से ले जाया जा सकता है कि किसी भी समय बहुभुज क्षेत्र के साथ इसका प्रतिच्छेदन एक उत्तल समूह है। एक मोनोटोन बहुभुज एक रेखा द्वारा घुमने योग्य होता है जो घुमने के दौरान अपना अभिविन्यास नहीं बदलता है। एक बहुभुज पूरी तरह से घुमने के योग्य होता है यदि उसके क्षेत्र का कोई भी भाग एक से अधिक बार घूमा न हो तो दोनों प्रकार की व्यापकता को द्विघात समय में पहचाना जाता है।[10]
3डी
उच्च आयामों के लिए बहुभुज की एकरूपता का एक भी सीधा सामान्यीकरण नहीं है।
एक दृष्टिकोण में संरक्षित मोनोटोनिकिटी लाइन L है। एक तीन आयामी पॉलीहेड्रॉन को दिशा L में 'कमजोर मोनोटोनिक' कहा जाता है यदि सभी रेखित-वर्ग लंबकोणीय L सरल बहुभुज हैं। यदि रेखित-वर्ग उत्तल हैं, तो पॉलीहेड्रॉन को 'उत्तल अर्थ में कमजोर मोनोटोनिक' कहा जाता है।[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.
