Voronoj-cellák és ekvidisztáns halmazok euklideszi terekben

Dátum
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

A dolgozatban a távolságmérés különböző módjaival és ahhoz kapcsolódó konstrukciókkal foglalkozunk.

Az első fejezetben bemutatjuk az infimum-metrikát és a Hausdorff-metrikát, ismertetjük ezek alapvető tulajdonságait, illetve szemügyre vesszük a legközelebbi pontok témakörét.

Egy véges halmaztól az infimum-távolság mérésének megkönnyítésére szolgál az ún. Voronoj-felbontás, amellyel a 2. fejezetben ismerkedünk meg. Ennek során a teret úgy bontjuk fel tartományokra ("cellákra"), hogy minden ilyenben egyértelmű legyen, az adott halmaz mely pontjától kell mérnünk a távolságot, vagyis a problémát visszavezetjük az eredeti metrika használatára. Ismertetjük a Voronoj-felbontás néhány alapvető tulajdonságát, pl. megvizsgáljuk, mikor lesz egy cella korlátos és összefüggő, valamint 2D-ben gráfelméleti vizsgálatokat is végzünk.

A harmadik fejezetben két adott halmaztól egyenlő távolságra lévő pontok halmazát, az ún. ekvidisztáns halmazokat vizsgáljuk először általános metrikus terekben, azután pedig euklideszi terekben. Vizsgáljuk az összefüggőségüket, illetve ismertetünk egy folytonossági tételt, amely a fókuszok véges halmazokkal való közelítése esetén lehetővé teszi az ekvidisztáns közelítő meghatározását. Emiatt külön hangsúlyt fektetünk a véges esetre, ezen esetekre bemutatunk egy algoritmust is.

A dolgozat zárásaként megmutatjuk, hogy minden konvex test határa előáll, mint ekvidisztáns halmaz, azaz hogy az ekvidisztáns halmazokat valamilyen értelemben a konvexitás általánosításának is tekinthetjük.

Leírás
Kulcsszavak
ekvidisztáns halmaz, Voronoj-cella, Hausdorff-metrika, legközelebbi pontok, konvex geometria, Voronoj-diagram
Forrás