بنية بيانات فعالة لأقرب مسافة Euclidean

Question

المسألة مستوحاة من مشكلة UVA التالية: https : //onlinejdudge.org/index.php؟ الخيار= OnlineJudge &؛ Itemid= 99999999 & الفئة= 18 و صفحة= show_problem & مشكلة= 1628 .

شبكة من محطات الحصول على البيانات ذات الحكم الذاتي، التي تعمل بالبطارية، تم تثبيتها لمراقبة المناخ في منطقة الأمازون. يمكن لمحطة إرسال الطلبات الشروع في نقل الإرشادات إلى محطات التحكم حتى يغيرون المعلمات الحالية. لتجنب زيادة التحميل الزائد للبطارية، يمكن لكل محطة (بما في ذلك محطة ترتيب الإرسال) إرسال فقط إلى محطتين أخريين. تتميز معاريز المحطة هي المحطتان الأقربتين. في حالة التعادل، فإن المعيار الأول هو اختيار أقصى غرب (أقصى اليسار على الخريطة)، والمعيار الثاني هو اختيار أقصى الجنوب (الأدنى على الخريطة). تقوم بتكليف من قبل حكومة ولاية أمازون كتابة برنامج يقرر إذا، بالنظر إلى توطين كل محطة، يمكن للرسائل الوصول إلى جميع المحطات.

الخوارزمية الساذجة بالطبع من شأنها بناء رسم بياني مع محطات كأدوات وحساب الحواف من قمة معينة من خلال البحث من خلال جميع القمم الأخرى لأقرب اثنين. ثم، يمكننا ببساطة تشغيل DFS / BFS. بالطبع، هذا يأخذ $ o (v ^ 2) $ الوقت لإنشاء الرسم البياني (الذي يمر حالات الاختبار). سؤالي، رغم ذلك، إذا استطعنا إنشاء الرسم البياني أي أسرع بنية بيانات مناسبة. على وجه التحديد، بالنظر إلى نقطة الاستعلام التعسفي $ P $ ومجموعة معينة من النقاط $ s $ ، هل يمكننا تنظيم النقاط في $ S $ في مثل هذه الطريقة التي يمكننا العثور عليها بسرعة أقرب النقاط في $ S $ إلى $ P $ (قل، في $ \ log v $ الوقت؟).

Answer 1

إذا فهمت هذا بشكل صحيح، يمكن استخدام معظم الفهارس المكانية.

الفهارس المكانية تحتوي عادة على $ o (log {v}) $ وقت الإدراج ووقت البحث المماثل لأقرب الجيران. بالطبع يمكنك إنشاء مخطط Voronoi من ذلك، ولكن يمكنك أيضا استخدام الفهرس مباشرة للعثور على أقرب جيران كلما احتجت إليهم.

للحصول على الأبعاد المنخفضة (2D، ثلاثي الأبعاد)، العائلات المشتركة للمهارس المكانية هي TREES KD (بسيطة للغاية وجيدة عموما، ولكن تميل إلى وجود مشاكل في مجموعات كثيفة من النقاط)، quadstrees (أصعب بعض الشيء لتنفيذ نفسك لأن الدقة العددية يمكن أن تكون صعبة) و r-tree (أصعب تنفيذه، ولكن إعطاء أفضل أداء مضمون، وخاصة شجرة R * (شجرة r-star)).

في حال كنت تستخدم C ++، إلقاء نظرة على libspatialindex أو تعزيز r-tree . إذا كنت تستخدم Java، فقم بإلقاء نظرة على My tinspin مكتبة.

المصطلح التقني لهذا هو " $ k $ أقرب استفسارات الجيران" أو " $ K $ -NN استفسارات "، مع $ K $ الرجوع إلى عدد أقرب الجيران الذي تريد العثور عليه.

Answer 2

يبدو أن هيكل البيانات ذات الصلة قد تكون ديناميكية مخطط voronoi .

مخططات Voronoi غالبا ما تكون الإجابة عندما تشارك مجموعة من النقاط على الطائرة.

في هذه الحالة، نظرا لأن مجموعة النقطة تتطور، فأنت تريد إصدار ديناميكي.