2010/06/09 by Christian Knauer, Knauer, Christian, Andreas Spillner +1
Computer Science · Engineering · Environmental Science · #3D Modeling in Geospatial Applications #Computational Geometry and Mesh Generation #Remote Sensing and LiDAR Applications
paper · doi:10.20382/jocg.v2i1a10
openalex publication_date 2010/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/06
A Manhattan network for a finite set P of points in the plane is a geometric graph such that its vertex set contains P, its edges are axis-parallel and non-crossing and, for any two points p andq in P, there exists a path in the network connecting p and q whose length equals the l1-distance between p and q. The problem of computing a Manhattan network of minimum total edge length for a given point set P has recently been shown to be NP-hard. In this note, using as the parameter the minimum number h of horizontal straight lines that contain the points in P, we present a fixed-parameter algorithm for this problem running in O*(214h) time and note that, under the exponential time hypothesis for 3-SAT, a run time that is subexponential in h is impossible.