Approximating minimum manhattan networks: (Extended abstract) Conference

Gudmundsson, J, Levcopoulos, C, Narasinihan, G. (1999). Approximating minimum manhattan networks: (Extended abstract) . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 1671 28-38. 10.1007/978-3-540-48413-4_4

cited authors

  • Gudmundsson, J; Levcopoulos, C; Narasinihan, G

abstract

  • Given a set S of n points in the plane, we define a Manhattan Network on S as a rectilinear network G with the property that for every pair of points in S, the network G contains the shortest rectilinear path between them. A Minimum Manhattan Network on S is a Manhattan network of minimum possible length. A Manhattan network can be thought of as a graph G = (V, E), where the vertex set V corresponds to points from S and a set of steiner points Sʹ, and the edges in E correspond to horizontal or vertical line segments connecting points in SUSʹ. A Manhattan network can also be thought of as a 1-spanner (for the L1-metric) for the points in S. Let R be an algorithm that produces a rectangulation of a staircase polygon in time R(n) of weight, at most, r times the optimal. We design an O(n log n + R(n)) time algorithm which, given a set. S of n points in the plane, produces a Manhattan network on S with total weight, at most. 4r times that, of a minimum Manhattan network. Using known rectangulation algorithms, this gives us an O(n3)-time algorithm with approximation factor four, and an O(n log n)-time algorithm with approximation factor eight.

publication date

  • January 1, 1999

published in

Digital Object Identifier (DOI)

start page

  • 28

end page

  • 38

volume

  • 1671