I detta dokument överväger vi närhetsproblem där frågorna är linjesegment i planet. Vi bygger en frågestruktur som för en uppsättning n punkter P kan bestämma den närmaste punkten i P till ett frågesegment utanför konvexa skrov av P i O(log n) tid. Med detta löser vi problemet med att beräkna den närmaste punkten till var och en av n separata linjesegment i O(n log3 n) tid. Närmaste utländska grannar eller HausdoriT avstånd för delade, färgade segment kan beräknas på samma gång. Vi utforskar några kopplingar till Hopcrofts problem.
Problemet med att lokalisera den närmaste punkten till en frågelinje segment bland en uppsättning P av n punkter i planet behandlades i REF.
Queries with segments in Voronoi diagrams
{'venue': "SODA '99", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}