WikiDer > Жақындық проблемалары - Википедия
Жақындық проблемалары проблемалар класы болып табылады есептеу геометриясы бағалауды қамтитын қашықтық геометриялық нысандар арасында.
Осы мәселелердің тек ұпай тұрғысынан берілген жиынтығы кейде деп аталады ең жақын нүктелік мәселелер,[1] дегенмен «ең жақын нүкте проблемасы» термині синоним ретінде қолданылады жақын көршіні іздеу.
Осы мәселелердің көпшілігіне тән қасиет - бұл орнату мүмкіндігі Θ(n журнал n) төменгі шекара олардың есептеу күрделілігі бастап азайту арқылы элементтің бірегейлігі проблемасы егер объектілер жиынтығы үшін қандай да бір минималды қашықтықты есептеудің тиімді алгоритмі болса, онда бұл арақашықтықтың 0-ге тең болатындығын тексеру өте маңызды емес екендігіне назар аудара отырып.
Атомдық мәселелер
Бұл проблемалар есептеу қиындықтары туындатпаса да, олардың кейбіреулері геометрияның компьютерлік қосымшаларында кең таралғандығымен ерекшеленеді.
- Жұбы арасындағы қашықтық сызық сегменттері. Оны бір формуламен өрнектеуге болмайды, мысалы, нүктеден сызыққа дейінгі қашықтық. Оны есептеу мүмкін конфигурацияларды, әсіресе 3D және одан жоғары өлшемдерде мұқият санауды талап етеді.[2]
- Шектеу қорабы, минималды оське тураланған гипер тікбұрыш онда барлық геометриялық мәліметтер бар
Ұпайлардағы мәселелер
- Ең жақын ұпайлар: N нүктесі берілгенде, олардың арасындағы қашықтық ең кіші екеуін табыңыз
- Ең жақын нүктелік сұрау / жақын көршінің сұрауы: N нүктесі берілгенде, берілген сұраныс нүктесіне дейінгі арақашықтық ең кішісін табыңыз
- Барлық жақын көршілердің проблемасы (құрылыс салу жақын көрші график): N нүктесін ескере отырып, олардың әрқайсысы үшін ең жақын нүктесін табыңыз
- Нүкте жиынтығының диаметрі: N нүктесі берілгенде, олардың арасындағы қашықтық ең үлкен екеуін табыңыз
- Нүкте жиынтығының ені: N нүктесі берілгенде, олардың арасындағы қашықтық ең кіші және олардың арасындағы барлық нүктелері бар екі (гипер) жазықтықты табыңыз
- Минималды созылатын ағаш ұпай жиынтығы үшін
- Delaunay триангуляциясы
- Вороной диаграммасы
- Ең кішкентай қоршау сферасы: N нүктесі берілгенде, олардың барлығын қоршап тұрған ең кіші сфераны (шеңберді) табыңыз
- Ең үлкен бос шеңбер: Жазықтықтағы N нүкте берілгенде, олардың шеңберінде центрленген ең үлкен шеңберді табыңыз дөңес корпус және олардың ешқайсысын қоршамайды
- Ең кішкентай қоршау тіктөртбұрышы: қарағанда қорап Жоғарыда айтылған мәселе, тіктөртбұрыш кез келген бағытта болуы мүмкін
- Ең үлкен бос төртбұрыш
- Геометриялық кілт, а өлшенген график нүктелердің жиынтығы бойынша, оның төбелері, әр төбенің жұбы үшін олардың арасындағы салмақтық жол ең көп дегенде «k» -дан, осы нүктелер арасындағы кеңістіктік қашықтықтан белгіленген «k» -дан артық болады.
Басқа
Әдебиеттер тізімі
- 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 тарауларда қарастырылған.
- ^ Дж. Р. Сак және Дж. Уррутия (ред.) (2000). Есептеу геометриясының анықтамалығы. Солтүстік Голландия. ISBN 0-444-82537-1.CS1 maint: қосымша мәтін: авторлар тізімі (сілтеме)
- ^ В.Люмельский (1985). «Сызық сегменттері арасындағы қашықтықты жылдам есептеу туралы». Инф. Процесс. Летт. 21 (2): 55–61. дои:10.1016/0020-0190(85)90032-8.