Кіріспе

Евклид геометриясындағы симпликалық кешен

Евклид кеңістігіндегі нүктелер жиынының триангуляциясы – бұл симпликалық кешен, ол нүктелер жиынының дөңгелек қабығын жабады, және оның төбелері жиынға тиесілі. Жазықтықта (егер нүктелер жиыны жазықтықтағы нүктелер болса), триангуляциялар үшбұрыштардан, олардың жиектерімен және төбелерімен бірге тұрады. Кейбір авторлар барлық нүктелер оның триангуляциясының төбелері болуын талап етеді. Бұл жағдайда, жазықтықтағы нүктелер жиынының триангуляциясын жазықтықтағы нүктелер арасындағы қиылыспайтын жиектердің максималды жиыны ретінде анықтауға болады. Триангуляциялар жазықтықтағы тура сызықты графиктердің ерекше жағдайлары болып табылады. Триангуляциялардың ерекше қызықты түрі – Делоне триангуляциясы. Олар Вороной диаграммаларының геометриялық дуалдары болып табылады. Жазықтықтағы нүктелер жиынының Делоне триангуляциясы Габриэль графигін, ең жақын көрші графигін және ең аз жабатын ағашты қамтиды. Триангуляциялардың көптеген қолданыс орындары бар, және белгілі бір өлшемшарттар бойынша берілген нүктелер жиынының «жақсы» триангуляциясын табуға қызығушылық бар, мысалы, ең аз салмақты триангуляциялар. Кейде арнайы қасиеттері бар триангуляция қажет, мысалы, барлық үшбұрыштардың үлкен бұрыштары болуы (ұзын және тар («ұсқынсыз») үшбұрыштардан аулақ болу). Жазықтықтағы нүктелерді байланыстыратын жиектер жиыны берілген жағдайда, олардың триангуляция құрайтынын анықтау мәселесі NP-толық.

Тұрақты үшбұрышты

Нүктелер жиынтығының кейбір үшбұрыштауларын, нүктелерін көтеру арқылы (яғни, әрбір нүктеге координата қосу арқылы), көтерілген нүктелер жиынтығының дөңгелек қабығын есептеу арқылы, және осы дөңгелек қабықтың төменгі жақтарын түпнұсқа кеңістікке проекциялау арқылы алуға болады. Осылай құрылған үшбұрыштаулар "тұрақты үшбұрыштаулар" деп аталады. Егер нүктелер y=x² теңдеуімен берілген параболоидқа көтерілсе, онда бұл құрылым Деланей үшбұрыштауын тудырады. Бұл құрылым үшбұрыштауды қамтамасыз ету үшін, көтерілген нүктелер жиынтығының төменгі дөңгелек қабығы симплекстік болуы керек. Деланей үшбұрыштауларының жағдайында, бұл талапқа сәйкес болу үшін, нүктелерінің ешқайсысы бір сфераның ішінде жатпауы керек.

Ұшақтағы комбинаторика

Жазықтықтағы кез келген нүктелер жиынының кез келген үшбұрыштауын үшбұрыштар мен жиектер құрайды, мұнда - бұл нүктелер санының шеңберлік қабық шекарасындағы саны. Бұл тура Эйлер сипаттамасының аргументінен туындайды.

Ұшақта үшбұрышты құру алгоритмдері

Үшбұрышты бөлу алгоритмі: Нүктелер жиынының дөңгелек қабығын табыңыз және осы қабықты көпбұрыш ретінде үшбұрыштарға бөліңіз. Ішкі нүктені таңдап, оны қамтитын үшбұрыштың үш төбесіне қабырғалар жүргізіңіз. Барлық ішкі нүктелер сарқылғанша осы процесті жалғастырыңыз. Үстемелі алгоритм: Нүктелерді x координаталары бойынша сұрыптаңыз. Алғашқы үш нүкте үшбұрышты анықтайды. Реттелген жиынның келесі нүктесін қарастырып, оны p-ге көрінетін барлық бұрын қарастырылған нүктелермен қосыңыз. Барлық нүктелер өңделгенге дейін бір-бірлеп нүкте қосу процесін жалғастырыңыз.