Utvidgningen av en Euclidean graf definieras som förhållandet mellan avståndet i grafen dividerat med avståndet i R d. I detta papper anser vi problemet med att placera roten av en stjärna så att utvidgning av den resulterande stjärnan är minimal. Vi presenterar en deterministisk O(n log n)-tid algoritm för att utvärdera utvidgning av en given stjärna; en randomiserad O(n log n) förväntad tid algoritm för att hitta en optimal center i R d ; och för fallet d = 2, en randomiserad O(n 2 α(n) log 2 n) förväntad tid algoritm för att hitta en optimal center bland inmatningspunkterna.
Ett partiellt svar på problem 8 gavs nyligen av Eppstein och Wortman REF som tillhandahöll en randomiserad O(n log n)-algoritm för beräkning av ett optimalt stjärncentrum för n-punkter i d-rymden.
Minimum dilation stars
{'venue': "SCG '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}