Vi anser att förbehandla en uppsättning S av n punkter i konvex position i planet till en datastruktur som stöder frågor i följande form: med tanke på en punkt q och en riktad linje i planet, rapportera den punkt i S som är längst från (eller, alternativt, närmast) den punkt q bland alla punkter till vänster om linjen. Vi presenterar två datastrukturer för detta problem. Den första datastrukturen använder O(n 1+ε ) utrymme och förbehandlingstid, och svarar på frågor i O(2 1/ε log n) tid, för alla 0 < ε < 1. Den andra datastrukturen använder O(n log 3 n) utrymme och polynom förbehandlingstid, och svarar på frågor i O(log n) tid. Dessa är de första lösningarna på problemet med O(log n) frågetid och o(n 2 ) utrymme. I den andra datastrukturen används en ny representation av närmaste och längst bort belägna Voronoi-diagram över punkter i konvex position. Denna representation stöder införandet av nya punkter i medurs ordning med endast O(log n) amortized pekaren ändringar, förutom O(log n)-tid punkt-lokalisering frågor, även om varje sådan uppdatering kan göra (n) kombinatoriska ändringar i Voronoi diagrammet. Denna datastruktur är den första demonstrationen att deterministiskt och stegvis konstruerade Voronoidiagram kan bibehållas i o(n) amorterade pekarändringar per operation samtidigt som O(log n)-tid punkt-lokalisering frågor.
Slutligen, i ett relaterat begränsat geometriskt sökproblem, Aronov et al. REF presenterar en datastruktur av storlek O(n log 3 n) som med tanke på en frågepunkt q och ett halvt plan h rapporterar närmaste eller längst bort till q men endast bland punkterna i S  och h i O(log n)-tid.
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}