Учитывая набор точек, где расстояние между ними равно расстоянию Манхэттена, и для каждой точки p a neighbour определяется как любая точка ниже p (на y-axis), которая находится в пределах или на юго-западе и юго-востоке диагонали, простирающиеся вниз от p; как мы можем эффективно перечислить для любого данного p ближайших соседей, которые не разделяют других соседей (которые находятся дальше от p)?
Например, для точки p ниже мы бы хотели только a и b (они ближе всего к p), потому что c и d являются neighbours как p, так и a и находятся дальше от p, чем a, но b не делит соседей с p.
p
a \
/ b
/c d/ \
Я бы предпочел до O(n) предварительной обработки времени и пространства. Я думал о предварительной обработке всех соответствующих диагоналей так, чтобы при заданной точке мы могли выполнять итерацию по каждой диагонали сверху вниз, где первый встретился с таким neighbour, остановит итерацию и укажет «треугольник» для разметки, где любая другая точку в таком треугольнике не нужно было бы пересматривать, но я не уверен, как реализовать такую "отметку" angular, и кажется, что может быть слишком много подразделений, чтобы быть эффективными.
Может ли эта проблема быть связана с выпуклой оболочкой?