I det här dokumentet presenterar vi en förbättrad algoritm för att hitta k närmast (lägre) poäng för ett givet godtyckligt frågesegment. Vi visar hur man prebehandlar en planaruppsättning P av n givna punkter i O(n 2 log n) förväntad tid (eller, alternativt, i O(n 2 log 2 n) deterministisk tid) och ett subkvadratiskt utrymme, för att rapportera k närmaste punkter till en godtycklig given frågelinje segment i O(k + log 2 n log n) tid. Här, för första gången, den datastruktur som ger polylogaritmisk frågetid och använder subquadratiskt utrymme presenteras. Vi visar också en algoritm för att rapportera k längst bort punkter från en godtycklig given frågelinje segment.
Segal och Zeitlin REF tillhandahöll en algoritm som tar O(log 2 n log n) frågetid, med hjälp av O(n 2 / log n) utrymme och O(n 2 ) förbehandlingstid.
Computing closest and farthest points for a query segment
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}