Yaqinlik muammolari - Proximity problems
Yaqinlik muammolari bu muammolarning sinfi hisoblash geometriyasi taxmin qilishni o'z ichiga olgan masofalar geometrik jismlar orasida.
Faqatgina punktlar bo'yicha bayon qilingan ushbu muammolarning bir qismi ba'zida ba'zan deb ataladi eng yaqin nuqta muammolari,[1] "eng yaqin nuqta muammosi" atamasi ham uchun sinonim sifatida ishlatiladi eng yaqin qo'shni qidirish.
Ushbu muammolarning aksariyati uchun umumiy xususiyat - bu imkoniyatni yaratishdir Θ (n jurnal n) pastki chegara ularning ustiga hisoblash murakkabligi dan kamaytirish orqali elementning o'ziga xosligi muammosi agar ob'ektlar to'plami uchun qandaydir minimal masofani hisoblash uchun samarali algoritm mavjud bo'lsa, bu masofaning 0 ga tengligini tekshirish juda ahamiyatli emasligini kuzatish asosida.
Atom muammolari
Ushbu muammolar hisoblashda hech qanday murakkablik tug'dirmasa ham, ularning ba'zilari geometriyaning kompyuter dasturlarida keng tarqalganligi bilan ajralib turadi.
- Juftlik orasidagi masofa chiziq segmentlari. Buni bitta formula bilan ifodalash mumkin emas, masalan, dan farqli o'laroq nuqtadan chiziqqa masofa. Uni hisoblash mumkin bo'lgan konfiguratsiyalarni, ayniqsa 3D va undan yuqori o'lchamlarda ehtiyotkorlik bilan sanab o'tishni talab qiladi.[2]
- Chegaralangan quti, minimal o'qqa tenglashtirilgan giper to'rtburchak tarkibida barcha geometrik ma'lumotlar mavjud
Ballar bo'yicha muammolar
- Eng yaqin juftliklar: N nuqta berilgan bo'lsa, ular orasidagi masofa eng kichik bo'lgan ikkitasini toping
- Eng yaqin nuqta so'rovi / eng yaqin qo'shni so'rovi: N ball berilgan bo'lsa, berilgan so'rov nuqtasiga eng kichik masofani toping
- Yaqin qo'shnilarning barcha muammolari (qurilish eng yaqin qo'shni grafigi ): N ball berilgan bo'lsa, ularning har biri uchun eng yaqinini toping
- Nuqta to'plamining diametri: N nuqta berilgan bo'lsa, ular orasidagi masofa eng katta ikkitasini toping
- Nuqta to'plamining kengligi: N nuqta berilgan bo'lsa, ular orasidagi masofa eng kichik bo'lgan va ular orasidagi barcha nuqtalar bo'lgan ikkita (giper) tekislikni toping
- Minimal uzunlikdagi daraxt ballar to'plami uchun
- Delaunay uchburchagi
- Voronoi diagrammasi
- Eng kichik yopiq shar: N nuqta berilgan bo'lsa, barchasini qamrab olgan eng kichik sharni (doirani) toping
- Eng katta bo'sh doira: Tekislikdagi N nuqta berilgan bo'lsa, ularning ichida markazlashgan eng katta doirani toping qavariq korpus va ularning hech birini qamrab olmaydi
- Eng kichik to'rtburchak: farqli o'laroq cheklovchi quti Yuqorida aytib o'tilgan muammo, to'rtburchak har qanday yo'nalishda bo'lishi mumkin
- Eng katta bo'sh to'rtburchak
- Geometrik kalit, a vaznli grafik har bir vertikal juftligi uchun og'irlik oralig'idagi yo'lga ega bo'lgan nuqtalar to'plami bo'ylab, bu "k" uchun bu nuqtalar orasidagi fazoviy masofadan ko'pi bilan "k" ga teng.
Boshqalar
Adabiyotlar
- Franko P. Preparata va Maykl Yan Shamos (1985). Hisoblash geometriyasi - kirish. Springer-Verlag. ISBN 0-387-96131-3. 1-nashr: ISBN 0-387-96131-3; 2-nashr, tuzatilgan va kengaytirilgan, 1988 yil: ISBN 3-540-96131-3; Ruscha tarjima, 1989 yil: ISBN 5-03-001041-6. Yaqinlik muammolari 6 va 7-boblarda keltirilgan.
- ^ J. R. Sack va J. Urrutiya (tahr.) (2000). Hisoblash geometriyasi bo'yicha qo'llanma. Shimoliy Gollandiya. ISBN 0-444-82537-1.CS1 maint: qo'shimcha matn: mualliflar ro'yxati (havola)
- ^ V. J. Lumelskiy (1985). "Chiziq segmentlari orasidagi masofani tezkor hisoblash to'g'risida". Inf. Jarayon. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.