Жақындық проблемалары - Proximity problems - Wikipedia

Жақындық проблемалары проблемалар класы болып табылады есептеу геометриясы бағалауды қамтитын қашықтық геометриялық нысандар арасында.

Осы мәселелердің тек ұпай тұрғысынан берілген жиынтығы кейде деп аталады ең жақын нүктелік мәселелер,[1] дегенмен «ең жақын нүкте проблемасы» термині синоним ретінде қолданылады жақын көршіні іздеу.

Осы мәселелердің көпшілігіне тән қасиет - бұл орнату мүмкіндігі Θ (n журнал n) төменгі шекара олардың есептеу күрделілігі бастап азайту арқылы элементтің бірегейлігі проблемасы егер объектілер жиынтығы үшін қандай да бір минималды қашықтықты есептеудің тиімді алгоритмі болса, онда бұл арақашықтықтың 0-ге тең болатындығын тексеру өте маңызды емес екендігіне назар аудара отырып.

Атомдық мәселелер

Бұл проблемалар есептеу қиындықтары туындатпаса да, олардың кейбіреулері геометрияның компьютерлік қосымшаларында кең таралғандығымен ерекшеленеді.

Ұпайлардағы мәселелер

Басқа

Әдебиеттер тізімі

  • Franco P. Preparata және Майкл Ян Шамос (1985). Есептеу геометриясы - кіріспе. Шпрингер-Верлаг. ISBN  0-387-96131-3. 1-ші басылым: ISBN  0-387-96131-3; 2-ші баспа, түзетілген және кеңейтілген, 1988 ж.: ISBN  3-540-96131-3; Орысша аудармасы, 1989: ISBN  5-03-001041-6. Жақындық проблемалары 6 және 7 тарауларда қарастырылған.
  1. ^ Дж. Р. Сак және Дж. Уррутия (ред.) (2000). Есептеу геометриясының анықтамалығы. Солтүстік Голландия. ISBN  0-444-82537-1.CS1 maint: қосымша мәтін: авторлар тізімі (сілтеме)
  2. ^ В.Люмельский (1985). «Сызық сегменттері арасындағы қашықтықты жылдам есептеу туралы». Инф. Процесс. Летт. 21 (2): 55–61. дои:10.1016/0020-0190(85)90032-8.