अभिकलनात्मक ज्यामिति
कम्प्यूटेशनल ज्यामिति में, एक स्वीप लाइन एल्गोरिथ्म या प्लेन स्वीप एल्गोरिथ्म एक एल्गोरिथम प्रतिमान है जो यूक्लिडियन अंतरिक्ष में विभिन्न समस्याओं को हल करने के लिए एक वैचारिक 'स्वीप लाइन' या 'स्वीप सतह' का उपयोग करता है। यह कम्प्यूटेशनल ज्यामिति में महत्वपूर्ण तकनीकों में से एक है।
इस प्रकार के एल्गोरिदम के पीछे का विचार यह कल्पना करना है कि एक रेखा (अक्सर एक लंबवत रेखा) कुछ बिंदुओं पर रुकते हुए विमान में बह जाती है या चली जाती है। ज्यामितीय प्रचालन ज्यामितीय वस्तुओं तक ही सीमित हैं जो या तो स्वीप लाइन को काटती हैं या जब भी यह बंद हो जाती हैं तो इसके आसपास के क्षेत्र में होती हैं, और एक बार रेखा सभी वस्तुओं के ऊपर से गुजरने के बाद पूरा समाधान उपलब्ध होता है।
इतिहास
इस दृष्टिकोण को कंप्यूटर चित्रलेख में रेंडरिंग के एल्गोरिदम को स्कैन करने के लिए खोजा जा सकता है, इसके बाद एकीकृत सर्किट लेआउट डिज़ाइन के शुरुआती एल्गोरिदम में इस दृष्टिकोण का दोहन किया जा सकता है, जिसमें एक आईसी के ज्यामितीय विवरण को समानांतर स्ट्रिप्स में संसाधित किया गया था क्योंकि संपूर्ण विवरण मेमोरी में फिट नहीं हो सका। .[citation needed]
अनुप्रयोग
इस दृष्टिकोण के अनुप्रयोग से ज्यामितीय एल्गोरिदम के एल्गोरिदम के विश्लेषण में एक सफलता मिली जब माइकल इयान शमोस और होए ने विमान में लाइन खंड चौराहे के लिए एल्गोरिदम प्रस्तुत किया, और विशेष रूप से, उन्होंने वर्णन किया कि कैसे कुशल डेटा संरचनाओं के साथ स्कैनलाइन दृष्टिकोण का संयोजन ( स्व-संतुलन बाइनरी सर्च ट्री ) यह पता लगाना संभव बनाता है कि क्या बीच में चौराहे हैं N समय जटिलता में विमान में खंड O(N log N).[1] बारीकी से संबंधित बेंटले-ओटमैन एल्गोरिथम सभी की रिपोर्ट करने के लिए स्वीप लाइन तकनीक का उपयोग करता है K किसी के बीच चौराहे N समय जटिलता में विमान में खंड O((N + K) log N) और अंतरिक्ष जटिलता O(N).[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].
