Linear-size planar Manhattan network for convex point sets

Let G = ( V , E ) be an edge weighted geometric graph (not necessarily planar) such that every edge is horizontal or vertical. The weight of an edge u v ∈ E is the L 1 -distance between its endpoints. Let W G ( u , v ) denotes the length of a shortest path between a pair of vertices u and v in G. The graph G is said to be a Manhattan network for a given point set P in the plane if P ⊆ V and ∀ p , q ∈ P , W G ( p , q ) = ‖ p q ‖ 1 . In addition to P, the graph G may also include a set T of Steiner points in its vertex set V. In the Manhattan network problem, the objective is to construct a Manhattan network of small size (the number of Steiner points) for a set of n points. This problem was first considered by Gudmundsson et al. [EuroCG 2007]. They give a construction of a Manhattan network of size Θ ( n log ⁡ n ) for general point sets in the plane. We say a Manhattan network is planar if it has a planar embedding. In this paper, we construct a planar Manhattan network for convex point sets in linear time using O ( n ) Steiner points. We also show that, even for convex point sets, the construction in Gudmundsson et al. [EuroCG 2007] needs Ω ( n log ⁡ n ) Steiner points, and the network may not be planar.