Геометриялық θ-графтары: Жақын көршілерге негізделген геометриялық құрылымдар

Кіріспе

Геометриялық шпанерлік графиктің түрі – геометриялық графиктер ең жақын көршілердің арасындағы кеңістікте анықталады. Есептеу геометриясында тета графигі немесе график – Яо графигіне ұқсас геометриялық шпанердің түрі. Құрылыстың негізгі әдісі әрбір төбе нүктесінің айналасындағы кеңістікті конустар жиынтығына бөлуді қамтиды, олар өздері графиктің қалған төбе нүктелерін бөледі. Яо графиктері сияқты, график конусқа ең көп дегенде бір қабырғаны қамтиды; олардың айырмашылығы – бұл қабырға қалай таңдалады. Яо графиктері графиктің метрикалық кеңістігіне сәйкес ең жақын нүктені таңдайды, ал тета графигі әр конуста (әдетте конустың биссектрисі) бар тұрақты сәулені анықтайды және сол сәулеге перпендикуляр проекцияларға қатысты ең жақын көршіні таңдайды. Нәтижесінде алынған графикте бірнеше жақсы шпанерлік қасиеттері бар. Тета графиктері алғаш рет Кларксонмен 1987 жылы және дербес түрде Кейлмен 1988 жылы сипатталған.

Құрылыс

графиктер олардың құрылымын анықтайтын бірнеше параметрлермен сипатталады. Ең нақты параметр – , ол әр төбесінің айналасындағы кеңістікті бөлетін тең бұрышты конустардың санына сәйкес келеді. Атап айтқанда, белгілі бір төбе үшін , оның үстінде бұрышпен арақашықтығы бар екі шексіз сәуле шығып тұратынын көзге елестетуге болады. Бұл конустар жазықтықты бөліп, графиктің қалған төбелер жиынын (жалпы жағдайды ескере отырып) , және тағы да , әр төбеге қатысты бірдей бағыттағы конустардың саны бірдей болады, ал біз әрқайсысына жататын төбелер жиынын қарастыра аламыз. Бір конусты қарастыра отырып, біз , шығатын тағы бір сәулені анықтауымыз керек. Графиктің әр төбесі үшін , әрқайсысының ортогональды проекциясын қарастырамыз. Егер , ең жақын проекциясы бар төбе болса, онда жиек графике қосылады. Бұл Яо графиктерінен басты айырмашылық, олар әрқашан ең жақын төбені таңдайды; мысал суретінде Яо графигі оның орнына жиекті қамтиды. Графиктің құрылысы сweepline алгоритмімен уақытта жүзеге асырылуы мүмкін. -қа , граф ең жақын көрші графты құрайды. -қа, графтың байланысты екенін көру оңай, себебі әр төбе сол жақтағы және оң жақтағы нәрсеге қосылады, егер олар болса. , , және -қа, графтың байланысты екені белгілі. Бұл нәтижелердің көптегені олардың аралық қатынастар шегін де көрсетеді. Егер саны жұп болса, біз жартылай граф деп аталатын графтың түрін құруға болады, онда конустар өздері кезегімен жұп және тақ жиынтықтарға бөлінеді, ал жиектер тек жұп конустарда (немесе тек тақ конустарда) қарастырылады. Жартылай графтардың өте жақсы қасиеттері бар екені белгілі. Мысалы, жартылай граф (және, демек, екі толық жартылай графтың бірігісі) 2-спанер болып табылады.

graphs are specified with a few parameters which determine their construction. The most obvious parameter is , which corresponds to the number of equal angle cones that partition the space around each vertex. In particular, for a vertex , a cone about can be imagined as two infinite rays emanating from it with angle between them. With respect to , we can label these cones as through in a counterclockwise pattern from , which conventionally opens so that its bisector has angle 0 with respect to the plane. As these cones partition the plane, they also partition the remaining vertex set of the graph (assuming general position) into the sets through , again with respect to Every vertex in the graph gets the same number of cones in the same orientation, and we can consider the set of vertices that fall into each. Considering a single cone, we need to specify another ray emanating from , which we will label For every vertex in , we consider the orthogonal projection of each onto Suppose that is the vertex with the closest such projection, then the edge is added to the graph. This is the primary difference from Yao Graphs which always select the nearest vertex; in the example image, a Yao Graph would include the edge instead. Construction of a graph is possible with a sweepline algorithm in time. For , the graph forms a nearest neighbor graph. For , it is easy to see that the graph is connected, as each vertex will connect to something to its left, and something to its right, if they exist. For , , , and , the graph is known to be connected. Many of these results also give upper and/or lower bounds on their spanning ratios. When is an even number, we can create a variant of the graph known as the half graph, where the cones themselves are partitioned into even and odd sets in an alternating fashion, and edges are only considered in the even cones (or, only the odd cones). Half graphs are known to have some very nice properties of their own. For example, the half graph (and, consequently, the graph, which is just the union of two complementary half graphs) is known to be a 2 spanner.