Abstrakt. Detta dokument beskriver en ny algoritm för att bygga uppsättningen av fria bitangenter av en samling av n separerade konvexa hinder av konstant komplexitet. Algoritmen körs i tid O(n log n + k), där k är utdatastorleken, och använder O(n) utrymme. Medan tidigare algoritmer uppnår samma optimala körtid, är detta den första optimala algoritmen som endast använder linjärt utrymme. Synlighetsgrafen eller synbarhetskomplexet kan beräknas i samma tid och rum. Den enda komplicerade datastruktur som används av algoritmen är en splittable kö, som kan genomföras enkelt med hjälp av röd-svarta träd. Algoritmen är konceptuellt mycket enkel och bör därför vara enkel att implementera och ganska snabb i praktiken. Algoritmen bygger på giriga pseudotriangulationer, som är subgrafer av synlighetsgrafen med många trevliga kombinatoriska egenskaper. Dessa egenskaper, och därmed algoritmens korrekthet, härrör delvis från egenskaper hos en viss partiell ordning på ytan av synlighetskomplexet.
När S innehåller n parvis separerade konvexa objekt av O(1) komplexitet var, problemet är lösbar i O(n log n + K) tid REF, där K = O(n 2 ) är antalet fria gemensamma tangenter.
Topologically Sweeping Visibility Complexes via Pseudotriangulations
{'venue': None, 'journal': 'Discrete & Computational Geometry', 'mag_field_of_study': ['Computer Science']}