Linear-size planar Manhattan network for convex point sets

DOI10.1016/J.COMGEO.2021.101819MaRDI QIDQ824337zbMATH OpenOpenAlexFDO

Authors Satyabrata Jana, Anil Maheshwari, Sasanka Roy

Publication date 15 December 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.06457

zbMATH Keywords

histogramplanar graphSteiner pointsconvex point setsManhattan network

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)

Abstract: Let $G=(V,E)$ be an edge-weighted geometric graph such that every edge is horizontal or vertical. The weight of an edge $uvinE$ is its length. Let $W_G(u,v)$ denote 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 $PsubseteqV$ and $forallp,qinP$, $W_G(p,q)=|pq{|}_1$. In addition to $P$, 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 for a set of $n$ points. This problem was first considered by Gudmundsson et al.cite{gudmundsson2007small}. They give a construction of a Manhattan network of size $Theta(nlogn)$ for general point set in the plane. We say a Manhattan network is planar if it can be embedded in the plane without any edge crossings. In this paper, we construct a linear size planar Manhattan network for convex point set in linear time using $mathcalO(n)$ Steiner points. We also show that, even for convex point set, the construction in Gudmundsson et al. cite{gudmundsson2007small} needs $Omega(nlogn)$ Steiner points and the network may not be planar.

Recommendations

• Planar point sets with large minimum convex decompositions
• Linear networks and convex polytopes
• Manhattan-geodesic embedding of planar graphs
• scientific article; zbMATH DE number 3885930
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
• On convex decompositions of a planar point set
• scientific article; zbMATH DE number 3845614
• Optimally fast incremental Manhattan plane embedding and planar tight span construction

Cites work

• scientific article; zbMATH DE number 4213490 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 140458 (Why is no real title available?)
• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A fixed-parameter algorithm for the minimum Manhattan network problem
• A plane 1.88-spanner for points in convex position
• A rounding algorithm for approximating minimum Manhattan networks
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• Algorithms and Computation
• Approximating a minimum Manhattan network
• Approximating the generalized minimum Manhattan network problem
• Geometric Spanner Networks
• Geometric biplane graphs. II: Graph augmentation
• Greedy construction of 2-approximate minimum Manhattan networks
• Minimum Manhattan network is NP-complete
• On rectilinear link distance
• On the stretch factor of Delaunay triangulations of points in convex position
• Planar graph decomposition and all pairs shortest paths
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• The minimum Manhattan network problem: Approximations and exact solutions
• The rectilinear Steiner arborescence problem
• The stretch factor of the Delaunay triangulation is less than 1.998

Cited in

(1)

• Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane

This page was built for publication: Linear-size planar Manhattan network for convex point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q824337)