अभिकलनात्मक ज्यामिति: Difference between revisions
(Created page with "{{Short description|Class of algorithms which use a moving line to solve geometrical problems}} File:Sweep-line-algorithm.gif|frame|right|फॉर्च्यून के...") |
(text) |
||
| Line 1: | Line 1: | ||
{{Short description|Class of algorithms which use a moving line to solve geometrical problems}} | {{Short description|Class of algorithms which use a moving line to solve geometrical problems}} | ||
[[File:Sweep-line-algorithm.gif|frame|right|फॉर्च्यून | [[File:Sweep-line-algorithm.gif|frame|right|फॉर्च्यून की कलन विधि का अनुप्राणन, [[वोरोनोई आरेख]]ों के निर्माण के लिए एक घुमाव रेखा तकनीक।]][[कम्प्यूटेशनल ज्यामिति|अभिकलनात्मक ज्यामिति]] में, एक घुमाव रेखा कलन विधि या समतलीय घुमाव कलन विधि एक [[एल्गोरिथम प्रतिमान|कलन विधि प्रतिमान]] है जो [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन स्थल]] में विभिन्न समस्याओं को हल करने के लिए एक वैचारिक 'घुमाव रेखा' या 'घुमाव सतह' का उपयोग करता है। यह अभिकलनात्मक ज्यामिति में महत्वपूर्ण तकनीकों में से एक है। | ||
इस प्रकार | इस प्रकार की कलन विधि के पीछे का विचार यह कल्पना करना है कि एक रेखा (प्रायः एक लंबवत रेखा) कुछ बिंदुओं पर रुकते हुए तल में बह जाती है या चली जाती है। ज्यामितीय प्रचालन ज्यामितीय वस्तुओं तक ही सीमित हैं जो या तो घुमाव रेखा को काटती हैं या जब भी यह बंद हो जाती हैं तो इसके आसपास के क्षेत्र में होती हैं, और एक बार रेखा सभी वस्तुओं के ऊपर से पारित होने के बाद पूरा समाधान उपलब्ध होता है। | ||
== इतिहास == | == इतिहास == | ||
इस दृष्टिकोण को [[ कंप्यूटर चित्रलेख ]] में | इस दृष्टिकोण को [[ कंप्यूटर चित्रलेख |कंप्यूटर चित्रलेख]] में प्रतिपादन के कलन विधि को क्रमवीक्षण करने के लिए खोजा जा सकता है, इसके बाद [[ एकीकृत सर्किट लेआउट |एकीकृत परिपथ विन्यास]] अभिकल्पना के प्रारम्भिक कलन विधि में इस दृष्टिकोण का दोहन किया जा सकता है, जिसमें एक आईसी के ज्यामितीय विवरण को समानांतर पट्टी में संसाधित किया गया था क्योंकि संपूर्ण विवरण मेमोरी में फिट नहीं हो सका। {{Citation needed|date=May 2009}} | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
इस दृष्टिकोण के अनुप्रयोग से ज्यामितीय | इस दृष्टिकोण के अनुप्रयोग से ज्यामितीय कलन विधि के कलन विधि के विश्लेषण में एक सफलता मिली जब [[माइकल इयान शमोस]] और होए ने तल में रेखा खंड प्रतिच्छेदन के लिए कलन विधि प्रस्तुत किया, और विशेष रूप से, उन्होंने वर्णन किया कि कैसे कुशल डेटा संरचनाओं (स्व-संतुलन युग्मक खोज ट्री) के साथ क्रमवीक्षण रेखा दृष्टिकोण का संयोजन यह पता लगाना संभव बनाता है कि {{math|[[Big O notation|O]](''N'' log ''N'')}} की समय जटिलता में तल में {{mvar|N}} खंड के बीच प्रतिच्छेदन हैं या नहीं। <ref>{{citation | ||
| last1 = Shamos | first1 = Michael I. | author1-link = Michael Ian Shamos | | last1 = Shamos | first1 = Michael I. | author1-link = Michael Ian Shamos | ||
| last2 = Hoey | first2 = Dan | | last2 = Hoey | first2 = Dan | ||
| Line 15: | Line 15: | ||
| pages = 208–215 | | pages = 208–215 | ||
| title = Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76) | | title = Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76) | ||
| year = 1976| s2cid = 124804 | url = http://euro.ecom.cmu.edu/shamos.html }}.</ref> | | year = 1976| s2cid = 124804 | url = http://euro.ecom.cmu.edu/shamos.html }}.</ref> निकटता से संबंधित बेंटले-ओटमैन एल्गोरिथ्म {{math|O((''N'' + ''K'') log ''N'')}} की समय जटिलता और {{math|O(''N'')}} की अंतरिक्ष जटिलता में तल में किसी भी {{mvar|N}} खंड के बीच सभी {{mvar|K}} प्रतिच्छेदन की प्रतिवेदन करने के लिए एक घुमाव रेखा तकनीक का उपयोग करता है। <ref>{{citation | ||
| last = Souvaine | first = Diane | author-link = Diane Souvaine | | last = Souvaine | first = Diane | author-link = Diane Souvaine | ||
| title = Line Segment Intersection Using a Sweep Line Algorithm | | title = Line Segment Intersection Using a Sweep Line Algorithm | ||
| url = https://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf | | url = https://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf | ||
| year = 2008}}.</ref> | | year = 2008}}.</ref> | ||
तब से, इस दृष्टिकोण का उपयोग कई समस्याओं के लिए कुशल | |||
तब से, इस दृष्टिकोण का उपयोग कई समस्याओं के लिए कुशल कलन विधि को अभिकल्पित करने के लिए किया गया है, जैसे कि वोरोनोई आरेख (फॉर्च्यून की कलन विधि) का निर्माण और बहुभुजों पर डेलाउने त्रिभुज या बूलियन संचालन। | |||
== सामान्यीकरण और विस्तार == | == सामान्यीकरण और विस्तार == | ||
सांस्थितिक व्यापक समतलीय घुमाव का एक रूप है जिसमें प्रसंस्करण बिंदुओं का एक सरल क्रम होता है, जो बिंदुओं को पूरी तरह से क्रमबद्ध करने की आवश्यकता से बचा जाता है; यह कुछ घुमाव रेखा कलन विधि को अधिक कुशलता से निष्पादित करने की अनुमति देता है। | |||
ज्यामितीय | ज्यामितीय कलन विधि को अभिकल्पित करने के लिए घूर्णी कैलीपर्स तकनीक को निविष्ट समतलीय के [[प्रोजेक्टिव डुअल|प्रक्षेपीय द्वैध]] में समतलीय घुमाव के रूप में भी व्याख्या किया जा सकता है: प्रक्षेपीय द्वैत का रूप एक रेखा के ढलान को एक समतलीय के एक्स-निर्देशांक में बदल देता है। दोहरे तल में बिंदु, इसलिए उनके ढलान द्वारा वर्गीकरण किए गए क्रम में रेखाों के माध्यम से प्रगति, जैसा कि एक [[घूर्णन कैलीपर्स]] कलन विधि द्वारा किया जाता है, एक तल घुमाव कलन विधि में उनके एक्स-निर्देशांक द्वारा क्रमबद्ध बिंदुओं के माध्यम से प्रगति के लिए दोहरी है। | ||
व्यापक दृष्टिकोण को उच्च आयामों के लिए सामान्यीकृत किया जा सकता है।<ref>{{cite arXiv |last=Sinclair |first=David |eprint=1602.04707 |title=A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation |class=cs.CG |date=2016-02-11}}</ref> | व्यापक दृष्टिकोण को उच्च आयामों के लिए सामान्यीकृत किया जा सकता है।<ref>{{cite arXiv |last=Sinclair |first=David |eprint=1602.04707 |title=A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation |class=cs.CG |date=2016-02-11}}</ref> | ||
Revision as of 09:23, 17 May 2023
अभिकलनात्मक ज्यामिति में, एक घुमाव रेखा कलन विधि या समतलीय घुमाव कलन विधि एक कलन विधि प्रतिमान है जो यूक्लिडियन स्थल में विभिन्न समस्याओं को हल करने के लिए एक वैचारिक 'घुमाव रेखा' या 'घुमाव सतह' का उपयोग करता है। यह अभिकलनात्मक ज्यामिति में महत्वपूर्ण तकनीकों में से एक है।
इस प्रकार की कलन विधि के पीछे का विचार यह कल्पना करना है कि एक रेखा (प्रायः एक लंबवत रेखा) कुछ बिंदुओं पर रुकते हुए तल में बह जाती है या चली जाती है। ज्यामितीय प्रचालन ज्यामितीय वस्तुओं तक ही सीमित हैं जो या तो घुमाव रेखा को काटती हैं या जब भी यह बंद हो जाती हैं तो इसके आसपास के क्षेत्र में होती हैं, और एक बार रेखा सभी वस्तुओं के ऊपर से पारित होने के बाद पूरा समाधान उपलब्ध होता है।
इतिहास
इस दृष्टिकोण को कंप्यूटर चित्रलेख में प्रतिपादन के कलन विधि को क्रमवीक्षण करने के लिए खोजा जा सकता है, इसके बाद एकीकृत परिपथ विन्यास अभिकल्पना के प्रारम्भिक कलन विधि में इस दृष्टिकोण का दोहन किया जा सकता है, जिसमें एक आईसी के ज्यामितीय विवरण को समानांतर पट्टी में संसाधित किया गया था क्योंकि संपूर्ण विवरण मेमोरी में फिट नहीं हो सका।[citation needed]
अनुप्रयोग
इस दृष्टिकोण के अनुप्रयोग से ज्यामितीय कलन विधि के कलन विधि के विश्लेषण में एक सफलता मिली जब माइकल इयान शमोस और होए ने तल में रेखा खंड प्रतिच्छेदन के लिए कलन विधि प्रस्तुत किया, और विशेष रूप से, उन्होंने वर्णन किया कि कैसे कुशल डेटा संरचनाओं (स्व-संतुलन युग्मक खोज ट्री) के साथ क्रमवीक्षण रेखा दृष्टिकोण का संयोजन यह पता लगाना संभव बनाता है कि O(N log N) की समय जटिलता में तल में N खंड के बीच प्रतिच्छेदन हैं या नहीं। [1] निकटता से संबंधित बेंटले-ओटमैन एल्गोरिथ्म O((N + K) log N) की समय जटिलता और O(N) की अंतरिक्ष जटिलता में तल में किसी भी N खंड के बीच सभी K प्रतिच्छेदन की प्रतिवेदन करने के लिए एक घुमाव रेखा तकनीक का उपयोग करता है। [2]
तब से, इस दृष्टिकोण का उपयोग कई समस्याओं के लिए कुशल कलन विधि को अभिकल्पित करने के लिए किया गया है, जैसे कि वोरोनोई आरेख (फॉर्च्यून की कलन विधि) का निर्माण और बहुभुजों पर डेलाउने त्रिभुज या बूलियन संचालन।
सामान्यीकरण और विस्तार
सांस्थितिक व्यापक समतलीय घुमाव का एक रूप है जिसमें प्रसंस्करण बिंदुओं का एक सरल क्रम होता है, जो बिंदुओं को पूरी तरह से क्रमबद्ध करने की आवश्यकता से बचा जाता है; यह कुछ घुमाव रेखा कलन विधि को अधिक कुशलता से निष्पादित करने की अनुमति देता है।
ज्यामितीय कलन विधि को अभिकल्पित करने के लिए घूर्णी कैलीपर्स तकनीक को निविष्ट समतलीय के प्रक्षेपीय द्वैध में समतलीय घुमाव के रूप में भी व्याख्या किया जा सकता है: प्रक्षेपीय द्वैत का रूप एक रेखा के ढलान को एक समतलीय के एक्स-निर्देशांक में बदल देता है। दोहरे तल में बिंदु, इसलिए उनके ढलान द्वारा वर्गीकरण किए गए क्रम में रेखाों के माध्यम से प्रगति, जैसा कि एक घूर्णन कैलीपर्स कलन विधि द्वारा किया जाता है, एक तल घुमाव कलन विधि में उनके एक्स-निर्देशांक द्वारा क्रमबद्ध बिंदुओं के माध्यम से प्रगति के लिए दोहरी है।
व्यापक दृष्टिकोण को उच्च आयामों के लिए सामान्यीकृत किया जा सकता है।[3]
संदर्भ
- ↑ Shamos, Michael I.; Hoey, Dan (1976), "Geometric intersection problems", Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76), pp. 208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.
- ↑ Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm (PDF).
- ↑ Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG].
