W przypadku płaskiego osadzenia wykresu płaskiego na płaszczyźnie o prostych krawędziach, zdefiniuj wierzchołek jako ostry wierzchołek, jeśli maksymalny kąt między dwiema kolejnymi krawędziami wokół niego jest większy niż 180. Innymi słowy, jeśli istnieje linia przechodząca przez ten wierzchołek wierzchołek w osadzeniu, tak że wszystkie krawędzie padające na ten wierzchołek leżą po jednej stronie linii, wówczas wierzchołek jest „ostry”, w przeciwnym razie nie. Ponadto martwmy się tylko o wierzchołki o stopniu co najmniej 3.
Chcę narysować wykresy płaskie z kilkoma ostrymi wierzchołkami. Czy ktoś wcześniej studiował takie rysunki?
W szczególności chcę narysować wykresy płaskie o maksymalnym stopniu 3, tak aby liczba ostrych wierzchołków stopnia 3 w osadzeniu wynosiła a współrzędne wierzchołków można zapisać wielomianową liczbą bitów.
Oto, co mogę znaleźć po spędzeniu czasu w Google Scholar:
Moja miara ostrości wierzchołka jest związana z już zbadaną koncepcją zwaną rozdzielczością kątową . Z Wikipedii:
Rozdzielczość kątowa rysunku wykresu odnosi się do najostrzejszego kąta utworzonego przez dowolne dwie krawędzie, które spotykają się na wspólnym wierzchołku rysunku.
Zatem rysunek płaski z rozdzielczością kątową wokół wierzchołków stopnia 3 będzie odpowiedni dla mojego celu.
W przypadku wierzchołka o stopniu na rysunku rozdzielczość kątowa wokół niego może wynosić najwyżej .
Pytanie o to, czy to jest ścisłe, było badane w przeszłości, ale mogę znaleźć tylko asymptotyczne wyniki. Na przykład Malitz i Papakostas dowodzą, że każdy płaski wykres o maksymalnym stopniu można narysować z rozdzielczością kątową . Ale ten wynik nie daje dobrych granic dla przypadku, gdy .