Rozwijająca się gwiazda
W geometrii obliczeniowej rozwinięcie gwiazdy wypukłego wielościanu to siatka uzyskana przez przecięcie wielościanu wzdłuż geodezji (najkrótsze ścieżki) przez jego ściany. Nazywano to również wewnętrznym układem wielościanu lub rozwijaniem Aleksandrowa od nazwiska Aleksandra Daniłowicza Aleksandrowa , który jako pierwszy to rozważał.
Opis
Bardziej szczegółowo, rozwinięcie gwiazdy uzyskuje się z wielościanu, punkt początkowy powierzchni, w ogólnej pozycji co oznacza, że istnieje unikalny punkt geodezyjny każdego . _ _ Wielokąt gwiazdy uzyskuje się przez przecięcie powierzchni. wzdłuż tych geodezji i rozłożenie powstałej powierzchni cięcia na płaszczyźnie . Powstały kształt tworzy prosty wielokąt na płaszczyźnie.
Rozwinięcie gwiazdy może służyć jako podstawa algorytmów czasu wielomianowego dla różnych innych problemów związanych z geodezją na wypukłych wielościanach.
Powiązane rozwinięcia
Rozwijanie gwiazdy należy odróżnić od innego sposobu cięcia wypukłego wielościanu w prostą sieć wielokątów, z rozwijaniem źródła . Rozwinięcie źródłowe przecina wielościan w punktach, które mają wiele równie krótkich geodezji do danego punktu bazowego i tworzy wielokąt z centrum środku, zachowując geodezję od . Zamiast tego rozwijająca się gwiazda przecina wielościan wzdłuż geodezji i tworzy wielokąt z wieloma kopiami na jego wierzchołkach. Pomimo ich nazw, rozwijające się źródło zawsze tworzy wielokąt w kształcie gwiazdy , ale rozwijająca się gwiazda nie.
Zbadano również uogólnienia rozwoju gwiazdy przy użyciu geodezyjnej lub quasi-geodezyjnej zamiast pojedynczego punktu bazowego. Inne uogólnienie wykorzystuje pojedynczy punkt bazowy i system geodezji, który niekoniecznie jest najkrótszą geodezją.
Ani rozwijająca się gwiazda, ani rozwijające się źródło nie ograniczają swoich cięć do krawędzi wielościanu. Otwartym problemem jest to, czy każdy wielościan można wyciąć i rozłożyć do prostego wielokąta, używając tylko cięć wzdłuż jego krawędzi.