Yakınlık sorunları - Proximity problems
Yakınlık sorunları bir sorun sınıfıdır hesaplamalı geometri tahminini içeren mesafeler geometrik nesneler arasında.
Yalnızca noktalar açısından belirtilen bu sorunların bir alt kümesine bazen şu şekilde atıfta bulunulur: en yakın nokta problemleri,[1] "en yakın nokta problemi" terimi aynı zamanda en yakın komşu araması.
Bu sorunların çoğu için ortak bir özellik, Θ (n günlük n) alt sınır üzerinde kendi hesaplama karmaşıklığı azaltarak element benzersizliği sorunu Bir nesne kümesi için bir tür minimum mesafeyi hesaplamak için etkili bir algoritma varsa, bu mesafenin 0'a eşit olup olmadığını kontrol etmenin önemsiz olduğu gözlemine dayanarak.
Atom sorunları
Bu problemler hesaplama karmaşıklığı sorunu oluşturmazken, bazıları geometrinin bilgisayar uygulamalarında her yerde bulunmaları nedeniyle dikkate değerdir.
- Bir çift arasındaki mesafe doğru parçaları. Örneğin, tek bir formülle ifade edilemez. bir noktadan bir çizgiye uzaklık. Hesaplaması, özellikle 3B ve daha yüksek boyutlarda olası konfigürasyonların dikkatli bir şekilde numaralandırılmasını gerektirir.[2]
- Sınırlayıcı kutu minimum eksen hizalı hiper dikdörtgen tüm geometrik verileri içeren
Puan problemleri
- En yakın puan çifti: N nokta verildiğinde, aralarında en küçük mesafeye sahip iki tane bulun
- En yakın nokta sorgusu / en yakın komşu sorgusu: N nokta verildiğinde, belirli bir sorgu noktasına en küçük mesafeyi bul
- En yakın komşular problemi ( en yakın komşu grafiği ): N puan verildiğinde, her biri için en yakın olanı bulun
- Bir nokta kümesinin çapı: N nokta verildiğinde, aralarında en büyük mesafeye sahip iki tane bulun
- Bir nokta kümesinin genişliği: N nokta verildiğinde, aralarında en küçük mesafeye ve aralarındaki tüm noktalara sahip iki (hiper) düzlem bulun
- Az yer kaplayan ağaç bir dizi nokta için
- Delaunay nirengi
- Voronoi diyagramı
- En küçük çevreleyen küre: N nokta verildiğinde, hepsini çevreleyen en küçük küre (daire) bulun
- En büyük boş daire: Düzlemde N nokta verildiğinde, bunların içinde ortalanmış en büyük çemberi bulun. dışbükey örtü ve hiçbirini çevrelemiyor
- En küçük çevreleyen dikdörtgen: aksine sınırlayıcı kutu yukarıda belirtilen sorun, dikdörtgen herhangi bir yönelimde olabilir
- En büyük boş dikdörtgen
- Geometrik anahtar, bir ağırlıklı grafik her köşe çifti için aralarında sabit bir 'k' için bu noktalar arasındaki uzamsal mesafenin en fazla 'k' katı ağırlıkta bir yola sahip olan köşeleri olarak bir nokta kümesi üzerinde.
Diğer
Referanslar
- Franco P. Preparata ve Michael Ian Shamos (1985). Hesaplamalı Geometri - Giriş. Springer-Verlag. ISBN 0-387-96131-3. 1. baskı: ISBN 0-387-96131-3; 2. baskı, düzeltilmiş ve genişletilmiş, 1988: ISBN 3-540-96131-3; Rusça çevirisi, 1989: ISBN 5-03-001041-6. Yakınlık sorunları 6. ve 7. bölümlerde ele alınmaktadır.
- ^ J. R. Sack ve J. Urrutia (editörler) (2000). Hesaplamalı Geometri El Kitabı. Kuzey Hollanda. ISBN 0-444-82537-1.CS1 bakimi: ek metin: yazarlar listesi (bağlantı)
- ^ V. J. Lumelsky (1985). "Çizgi parçaları arasındaki mesafenin hızlı hesaplanması üzerine". Inf. İşlem. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.