एल्गोरिथ्म सेट बी में सेट एक निकटतम पड़ोसी में सभी बिंदुओं के लिए खोजने के लिए

Question

मान लीजिए हम अंक ए, बी के दो सेट है, और हम सेट बी में सेट एक अपने निकटतम पड़ोसी में प्रत्येक बिंदु के लिए प्राप्त करना चाहते

एक बिंदु के लिए निकटतम पड़ोसी को खोजने के लिए कई अच्छे एल्गोरिदम हैं। क्या ए_1 के लिए हमें मिली जानकारी का उपयोग करने का कोई तरीका है, सेट में ए 2 या अन्य बिंदुओं के लिए निकटतम पड़ोसी के लिए अधिक कुशलतापूर्वक खोज करना?

मैं कुछ ऐसा सोच रहा हूं: बी और नए बिंदु ए 2 में प्रत्येक बिंदु के बीच संभावित दूरी के लिए अंतराल प्राप्त करने के लिए त्रिभुज अतुल्यता का उपयोग करें, और अंतराल के अधिकतम और मिनट को क्रमबद्ध करें, और फिर मैं केवल बी में अंक खोज सकता हूं जो पहले अंतराल में पड़ता है।

Answer 1

1. सेट बी के अंक के लिए Voronoi diagram खोजें
2. सेट ए और सेट बी के Voronoi चित्र के अंक के ऊपर एक Sweep line algorithm लागू जहाँ भी झाडू लाइन सेट एक से कुछ बिंदु शामिल हैं, Voronoi इस चित्र की जो किनारों के बीच लग रही है बिंदु स्थित है। यह इस बिंदु से संबंधित वोरोनोई आरेख का कौन सा चेहरा निर्धारित करने की अनुमति देता है। जो सेट बी

चरण 2 के लिए विवरण: कुछ आदेशित कंटेनर में वर्तमान में स्वीप लाइन द्वारा छेड़छाड़ किए गए वोरोनोई आरेख के सभी किनारों को रखें। जब स्वीप लाइन वोरोनोई आरेख के कुछ कशेरुक को कवर करती है, तो किनारों को हटाएं/जोड़ दें, इस कशेरुक को घटना से/कंटेनर तक। देखने के लिए, किस बिंदु के किनारे किनारों पर स्थित है, कंटेनर में इस बिंदु पर उत्तराधिकारी/पूर्ववर्ती किनारों को प्राप्त करें।

समय जटिलता ओ ((एम + एन) लॉग एम है)। एन = | ए |, एम = | बी |

Answer 2

आपको "कुशल प्रोग्राम लिखने" के बेंटले पढ़ने से लाभ हो सकता है, जहां वह यात्रा विक्रेता कार्यक्रम के केस स्टडी से संबंधित है। उन्होंने जो बचत की पहचान की वह एक था कि दो बिंदुओं के बीच विसर्जन एक वर्ग रूट लेने में शामिल था जो महंगा था। वर्ग रूट लेना आपको वास्तविक दूरी देता है, वर्ग रूट नहीं लेना आपको एक संख्या देता है जिसका उपयोग अन्य सापेक्ष मूल्यों के मुकाबले तुलना करने के लिए किया जा सकता है।

मैं पुस्तक को पढ़ने की अत्यधिक अनुशंसा करता हूं। यह आपके मस्तिष्क को सही जगह पर रखेगा।

Answer 3

एक ब्रूट फोर्स समाधान सेट बी के निकटतम बिंदुओं के डेंडोग्राम का उपयोग करने के लिए हो सकता है। फिर सेट ए के प्रत्येक बिंदु को डेंडोग्राम से तुलना करें। आप डेलोग्राम त्रिभुज के साथ डेंडोग्राम भी बना सकते हैं।