Vi presenterar en algoritm som beräknar en kortaste icke-avtalsbar och en kortaste icke-skiljande cykel på en orientalisk kombinatorisk yta av avgränsat släkte i O(n log n) tid, där n betecknar komplexiteten i ytan. Detta löser ett centralt öppet problem i beräkningstopologi, förbättra på den nuvarande-bästa O(n 3/2 )-tidsalgoritm av Cabello och Mohar (ESA 2005). Vår algoritm är baserad på universal-cover konstruktioner för att hitta korta cykler och använder sig i stor utsträckning av befintliga verktyg från fältet. disk och Colin de Verdière och Lasarus [7] visade hur man sönderdelar en viss yta i delar av släktet 0. Senare verk av Erickson och Whittlesey [11] och Colin de Verdière och Erickson [5] behandlar beräkning av korta generatorer av den grundläggande gruppen och kortaste vägar och cykler i givna homotopy klasser. En central öppen fråga som uppstod i detta sammanhang är: (P) Hur beräknar man en kortaste icke-trivial cykel på en topologisk yta effektivt?
Nyligen presenterar REF en algoritm som beräknar en kortaste icke-trivial cykel i O(n log n) på en orientalisk kombinatorisk yta av avgränsat släkte.
Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time
{'venue': "SCG '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}