मोनोटोन बहुभुज: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| Line 1: | Line 1: | ||
[[File:M-polygon.svg|thumb|right|हरा एक चौराहे को | [[File:M-polygon.svg|thumb|right|हरा एक चौराहे को दर्शाता है, नीला दो चौराहों को दर्शाता करता है, और लाल तीन या अधिक को दर्शाता है। शीर्ष दो बहुभुज L के संबंध में मोनोटोन हैं जबकि नीचे के दो बहुभुज नहीं हैं।]][[ज्यामिति]] में, समतल में एक [[बहुभुज]] P को एक सीधी रेखा L के संबंध में 'मोनोटोन' कहा जाता है, यदि L के लिए लंबकोणीय प्रत्येक रेखा P की सीमा को अधिक से अधिक दो बार काटती है।<ref name=PS>{{citation|first1=Franco P.|last1=Preparata|author1-link=Franco P. Preparata|first2=Michael Ian|last2=Shamos|author2-link=Michael Ian Shamos|title=Computational Geometry – An Introduction|publisher=[[Springer-Verlag]]|year=1985|id=1st edition: ; 2nd printing, corrected and expanded, 1988: ; Russian translation, 1989|isbn=0-387-96131-3|url-access=registration|url=https://archive.org/details/computationalgeo0000prep}}</ref> | ||
इसी | इसी के अनुसार, एक [[बहुभुज श्रृंखला]] C को एक सीधी रेखा L के संबंध में 'मोनोटोन' कहा जाता है, यदि प्रत्येक रेखा L के लिए लंबकोणीय C को अधिक से अधिक एक बार काटती है। | ||
कई | कई प्रयोगात्मक उद्देश्यों के लिए इस परिभाषा को ऐसे स्थितियो की अनुमति देने के लिए विस्तारित किया जा सकता है जब p के कुछ किनारे L के लिए लंबकोणीय होते हैं, यदि एक रेखा खंड जो p में दो बिंदुओं को जोड़ता है और L के लिए लंबकोणीय है, p में पूरी तरह से स्थित है। तो एक [[साधारण बहुभुज]] को मोनोटोन कहा जा सकता है | ||
मोनोटोन | मोनोटोन फलनो के लिए शब्दावली के बाद, पूर्व परिभाषा L के संबंध में 'बहुभुजों को सख्ती से मोनोटोन' का वर्णन करती है। | ||
== गुण == | == गुण == | ||
मान लें कि | मान लें कि L X-अक्ष के संपाती है। फिर एक [[मोनोटोनिक]] बहुभुज के बाएँ और दाएँ कोने अपनी सीमा को दो मोनोटोन बहुभुज श्रृंखलाओं में विघटित कर देते हैं, जैसे कि जब किसी श्रृंखला के शीर्षों को उनके प्राकृतिक क्रम में पार किया जा रहा हो, तो उनके X-निर्देशांक एकरस रूप से बढ़ रहे हैं या घट रहे हैं। यथार्थ, इस गुण को मोनोटोन बहुभुज की परिभाषा के लिए लिया जा सकता है और यह बहुभुज को अपना नाम देता है। | ||
एक [[उत्तल बहुभुज]] किसी भी सीधी रेखा के संबंध में मोनोटोन होता है और एक बहुभुज जो प्रत्येक सीधी रेखा के संबंध में मोनोटोन होता है वह उत्तल होता है। | एक [[उत्तल बहुभुज]] किसी भी सीधी रेखा के संबंध में मोनोटोन होता है और एक बहुभुज जो प्रत्येक सीधी रेखा के संबंध में मोनोटोन होता है वह उत्तल होता है। | ||
एक रैखिक समय | एक रैखिक समय कलन विधि सभी दिशाओं की सूचना देने के लिए जाना जाता है जिसमें एक दिया गया सरल बहुभुज मोनोटोन होता है।<ref>{{citation|first1=Franco P.|last1=Preparata|author1-link=Franco P. Preparata|first2=Kenneth J.|last2=Supowit|title=Testing a simple polygon for monotonicity|journal=[[Information Processing Letters]]|volume=12|issue=4|year=1981|pages=161–164|doi=10.1016/0020-0190(81)90091-0}}.</ref> एक साधारण बहुभुज को दो मोनोटोन श्रृंखलाओं (संभवतः अलग-अलग दिशाओं में एकरस) में विघटित करने के सभीविधियो की सूचना देने के लिए सामान्यीकृत किया गया था।<ref>{{citation|first1=David|last1=Rappaport|first2=Arnold|last2=Rosenbloom|title=Moldable and castable polygons|journal=Computational Geometry|volume=4|issue=4|pages=219–233|year=1994|doi=10.1016/0925-7721(94)90020-5|doi-access=free}}.</ref> | ||
एक मोनोटोन बहुभुज के संबंध में बहुभुज प्रश्नों में बिंदुओं का उत्तर [[रैखिक समय]] पूर्वप्रक्रमण के बाद [[लघुगणकीय समय]] में दिया जा सकता है (बाएं और सबसे दाएं कोने खोजने के लिए)।<ref name="PS" /> | |||
[[File:Polygon-to-monotone.png|thumb|एक बहुभुज को मोनोटोन बहुभुजों में तोड़ना]]एक साधारण बहुभुज आसानी से बहुभुज त्रिकोणासन हो सकता है | एक मोनोटोन बहुभुज को रेखीय समय में आसानी से त्रिभुजित किया जा सकता है।<ref>{{citation |last1=Fournier |first1=A. |author1-link=Alain Fournier |last2=Montuno |first2=D. Y. |title=Triangulating simple polygons and equivalent problems |journal=[[ACM Transactions on Graphics]] |volume=3 |issue=2 | year=1984 <!--|month=April--> |pages=153–174 |issn=0730-0301 |doi=10.1145/357337.357341|s2cid=33344266 }}</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) समय में एक साधारण बहुभुज आसानी से बहुभुज त्रिकोणासन हो सकता है करना। चूंकि एक त्रिभुज एक मोनोटोन बहुभुज है, बहुभुज त्रिभुज यथार्थ एक बहुभुज को मोनोटोन वाले में काट रहा है, और यह 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 | ||
| Line 26: | Line 28: | ||
| pages=485–524 | | pages=485–524 | ||
| issn=0179-5376 | | issn=0179-5376 | ||
| doi=10.1007/BF02574703 | doi-access=free}}</ref> रैखिक अपेक्षित समय के साथ एक सरल यादृच्छिक | | doi=10.1007/BF02574703 | doi-access=free}}</ref> रैखिक अपेक्षित समय के साथ एक सरल यादृच्छिक कलां विधि भी जाना गया है।<ref>{{citation | ||
| last1=Amato | first1=Nancy M. | author1-link = Nancy M. Amato | | last1=Amato | first1=Nancy M. | author1-link = Nancy M. Amato | ||
| last2=Goodrich | first2=Michael T. | author2-link=Michael T. Goodrich | | last2=Goodrich | first2=Michael T. | author2-link=Michael T. Goodrich | ||
| Line 39: | Line 41: | ||
|url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185 | |url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185 | ||
| issue=2}}</ref> | | issue=2}}</ref> | ||
एक साधारण बहुभुज को समान रूप से मोनोटोन बहुभुजों की न्यूनतम संख्या में काटना (अर्थात्, एक ही पंक्ति के संबंध में मोनोटोन) बहुपद समय में किया जा सकता है।<ref>{{citation|title=On decomposing polygons into uniformly monotone parts|first=Robin|last=Liu|year=1988|journal=[[Information Processing Letters]]|volume=27|issue=2|pages=85–89|doi=10.1016/0020-0190(88)90097-X}}.</ref> | |||
[[गति योजना]] के संदर्भ में, दो गैर-अंतर्विभाजक मोनोटोन बहुभुज एक ही अनुवाद द्वारा अलग-अलग होते हैं ( | |||
[[गति योजना]] के संदर्भ में, दो गैर-अंतर्विभाजक मोनोटोन बहुभुज एक ही अनुवाद द्वारा अलग-अलग होते हैं (अर्थात्, एक बहुभुज का अनुवाद उपस्थित होता है जैसे कि दो अलग-अलग आधा समतलो में सीधी रेखा से अलग हो जाते हैं) और यह पृथकत्व रैखिक समय में पाया जा सकता है .<ref name="telg">{{citation|last1=Toussaint|first1=G. T.|author1-link=Godfried Toussaint|last2=El Gindy|first2=H. A.|title=Separation of two monotone polygons in linear time|journal=Robotica|volume=2|issue=4|year=1984|pages=215–220|doi=10.1017/S0263574700008924}}.</ref> | |||
== सामान्यीकरण == | == सामान्यीकरण == | ||
=== | === घुमने के योग्य बहुभुज === | ||
एक बहुभुज को | एक बहुभुज को व्यापक कहा जाता है,यदि एक सीधी रेखा को पूरे बहुभुज पर लगातार इस तरह से ले जाया जा सकता है कि किसी भी समय बहुभुज क्षेत्र के साथ इसका प्रतिच्छेदन एक उत्तल समूह है। एक मोनोटोन बहुभुज एक रेखा द्वारा घुमने योग्य होता है जो घुमने के दौरान अपना अभिविन्यास नहीं बदलता है। एक बहुभुज पूरी तरह से घुमने के योग्य होता है यदि उसके क्षेत्र का कोई भी भाग एक से अधिक बार घूमा न हो तो दोनों प्रकार की व्यापकता को द्विघात समय में पहचाना जाता है।<ref name=bk>{{citation|title=Generalizing monotonicity: On recognizing special classes of polygons and polyhedra by computing nice sweeps|first1=Prosenjit|last1=Bose|author1-link=Jit Bose|first2=Marc|last2=van Kreveld|journal=International Journal of Computational Geometry & Applications|volume=15|issue=6|year=2005|doi=10.1142/S0218195905001877|pages=591–608|hdl=1874/24150|hdl-access=free}}.</ref> | ||
| Line 53: | Line 57: | ||
उच्च आयामों के लिए बहुभुज की एकरूपता का एक भी सीधा सामान्यीकरण नहीं है। | उच्च आयामों के लिए बहुभुज की एकरूपता का एक भी सीधा सामान्यीकरण नहीं है। | ||
एक दृष्टिकोण में संरक्षित | एक दृष्टिकोण में संरक्षित मोनोटोनिकिटी लाइन L है। एक तीन आयामी पॉलीहेड्रॉन को दिशा L में 'कमजोर मोनोटोनिक' कहा जाता है यदि सभी रेखित-वर्ग लंबकोणीय L सरल बहुभुज हैं। यदि रेखित-वर्ग उत्तल हैं, तो पॉलीहेड्रॉन को 'उत्तल अर्थ में कमजोर मोनोटोनिक' कहा जाता है।<ref name=telg/>बहुपद समय में दोनों प्रकारों को पहचाना जा सकता है।<ref name=bk/> | ||
एक अन्य दृष्टिकोण में संरक्षित एक आयामी विशेषता | एक अन्य दृष्टिकोण में संरक्षित एक आयामी विशेषता लंबकोणीय दिशा है। यह तीन आयामों में [[बहुफलकीय भूभाग]] की धारणा के लिए जन्म देता है: इस गुण के साथ एक पॉलीहेड्रल सतह जो प्रत्येक लंबवत (अर्थात्, जेड अक्ष के समानांतर) रेखा सतह को एक बिंदु या खंड से अधिक से अधिक काटती है। | ||
== यह भी देखें == | == यह भी देखें == | ||
*[[ऑर्थोगोनल उत्तलता]], पॉलीगोन के लिए जो दो परस्पर | *[[ऑर्थोगोनल उत्तलता|लंबकोणीय उत्तलता]], पॉलीगोन के लिए जो दो परस्पर लंबकोणीय दिशाओं के संबंध में एक साथ मोनोटोन हैं; निश्चित दिशाओं की किसी भी संख्या के लिए एक सामान्यीकरण भी। | ||
*सि[[तारे के आकार का बहुभुज]], मोनोटोन बहुभुजों का एक ध्रुवीय निर्देशांक एनालॉग | *सि[[तारे के आकार का बहुभुज]], मोनोटोन बहुभुजों का एक ध्रुवीय निर्देशांक एनालॉग | ||
Revision as of 12:13, 29 November 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.
