Problémy s blízkostí - Proximity problems - Wikipedia
Problémy s blízkostí je třída problémů v výpočetní geometrie které zahrnují odhad vzdálenosti mezi geometrickými objekty.
Podmnožina těchto problémů uvedená pouze z hlediska bodů se někdy označuje jako problémy s nejbližším bodem,[1] ačkoli termín "problém nejbližšího bodu" je také používán synonymně k hledání nejbližšího souseda.
Společným rysem mnoha z těchto problémů je možnost založit Θ (n log n) dolní mez Na jejich výpočetní složitost snížením z problém jedinečnosti prvku na základě pozorování, že pokud existuje efektivní algoritmus pro výpočet nějaké minimální vzdálenosti pro sadu objektů, je triviální zkontrolovat, zda se tato vzdálenost rovná 0.
Atomové problémy
I když tyto problémy nepředstavují výzvu pro výpočetní složitost, některé z nich jsou pozoruhodné díky své všudypřítomnosti v počítačových aplikacích geometrie.
- Vzdálenost mezi dvojicí úsečky. Nelze jej vyjádřit jediným vzorcem, na rozdíl od např vzdálenost od bodu k přímce. Jeho výpočet vyžaduje pečlivý výčet možných konfigurací, zejména ve 3D a vyšších rozměrech.[2]
- Ohraničující rámeček, minimální osa zarovnána hyperrektangle který obsahuje všechna geometrická data
Problémy v bodech
- Nejbližší pár bodů: Vzhledem k N bodům najděte dva s nejmenší vzdáleností mezi nimi
- Nejbližší bodový dotaz / dotaz na nejbližšího souseda: Vzhledem k N bodům najděte jeden s nejmenší vzdáleností od daného bodu dotazu
- Problém všech nejbližších sousedů (výstavba graf nejbližšího souseda ): Vzhledem k počtu N bodů najděte pro každý z nich nejbližší
- Průměr množiny bodů: Vzhledem k N bodům najděte dva s největší vzdáleností mezi nimi
- Šířka množiny bodů: Vzhledem k N bodům najděte dvě (hyper) roviny s nejmenší vzdáleností mezi nimi a se všemi body mezi nimi
- Minimální kostra za sadu bodů
- Delaunayova triangulace
- Voronoiho diagram
- Nejmenší obklopující koule: Vzhledem k N bodům najděte nejmenší kouli (kruh), která je všechny obklopuje
- Největší prázdný kruh: Vzhledem k tomu, že v rovině je N bodů, najděte největší kruh uprostřed konvexní obal a žádný z nich neuzavřel
- Nejmenší uzavírací obdélník: na rozdíl od ohraničující rámeček výše uvedený problém může mít obdélník libovolné orientace
- Největší prázdný obdélník
- Geometrický klíč, a vážený graf přes sadu bodů jako její vrcholy, které pro každou dvojici vrcholů mají cestu mezi nimi o hmotnosti nejvýše 'k' krát prostorovou vzdálenost mezi těmito body pro pevné 'k'.
jiný
Reference
- Franco P. Preparata a Michael Ian Shamos (1985). Výpočetní geometrie - úvod. Springer-Verlag. ISBN 0-387-96131-3. 1. vydání: ISBN 0-387-96131-3; 2. tisk, opraveno a rozšířeno, 1988: ISBN 3-540-96131-3; Ruský překlad, 1989: ISBN 5-03-001041-6. Problémy s blízkostí jsou popsány v kapitolách 6 a 7.
- ^ J. R. Sack a J. Urrutia (eds.) (2000). Příručka výpočetní geometrie. Severní Holandsko. ISBN 0-444-82537-1.CS1 maint: další text: seznam autorů (odkaz)
- ^ V. J. Lumelsky (1985). "Při rychlém výpočtu vzdálenosti mezi úsečkami". Inf. Proces. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.