International Journal of Computational Geometry & Applications

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem.

1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2. Each embedding of a closed convex curve has dilation ≥ 1.00157.

3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation .

Given a point set K of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical, or ±45° diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the so-called X-architecture.

As the related rectilinear and the Euclidian Steiner tree problem are well-known to be NP-hard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NP-completeness of the decision version of the octilinear Steiner tree problem.

We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a planar graph of size which contains a (1 + ε)–approximation of a minimum octilinear Steiner tree for every ε > 0 and n = |K|. Hence, we can apply any α–approximation algorithm for the Steiner tree problem in graphs (for planar graphs, Borradaile et al. very recently presented a polynomial time approximation scheme) and achieve an (α + ε)–approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons).

Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in d-D images (d ≥ 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several layered net surface (LNS) problems captured by an interesting type of geometric graphs called ordered multi-column graphs in the d-D discrete space (d ≥ 3 is any constant integer). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the d-D LNS problem (d ≥ 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures and thus admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related net surface volume (NSV) problems of computing well-shaped geometric regions of an optimal total volume in a d-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. Experiments and comparisons based on real medical data showed that our LNS algorithms and software are computationally efficient and produce highly accurate and consistent segmentation results.