Fast maintenance of rectilinear centers Academic Article uri icon


  • We address the problem of dynamic maintenance of 2-centers in the plane under rectilinear metric.We present two algorithms for the continuous and discrete versions of the problem. We show that rectilinear 2-centers can be maintained in O(log2 n) time. We give an algorithm for semi-dynamic (either insertions only or deletions only) maintenance of the discrete 2-centers in O(log n log m) amortized time where n is the number of customer points and m is the number of possible locations of centers.

publication date

  • January 1, 2001