Vi anser följande problem: med tanke på en enkel polygon P och en stjärnformad polygon V, nd en punkt (eller uppsättning av punkter) i P där den del av P som är synlig är översättning-kongruent till V. Problemet uppstår i lokaliseringen av robotar utrustade med ett avstånd-nder och en kompass  på P är en karta över en känd miljö, V är den del som syns från robotens position, och roboten måste använda denna information för att bestämma sin position i kartan. Vi ger ett schema som förbehandlar P så att varje efterföljande fråga V besvaras i optimal tid O(m + log n + A), där m och n är antalet hörn i V och P, och A är antalet punkter i P som är giltiga svar (utdatastorleken). Vår teknik använder O(n 5 ) utrymme och förbehandling i värsta fall; inom vissa gränser kan vi handla o smidigt mellan frågetiden och förbehandlingen tid och utrymme. I processen för att lösa detta problem, vi utformar också en datastruktur för utdatakänslig bestämning av synlighet polygon av en frågepunkt inuti en polygon P. Vi överväger sedan en variant av lokaliseringsproblem där det finns ett maximalt avstånd som roboten kan \se"  och detta motiveras av praktiska överväganden, och vi skisserar en liknande lösning för detta fall. Vi visar nally att en enda localization fråga V kan besvaras i tid O (mn) utan förbehandling.
Ghodsi m.fl. REF minskade frågetiden för enkla polygoner till O(log n+k), på bekostnad av förbehandling som krävde O(n 3 ) tid och utrymme.
The Robot Localization Problem
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}