Minimal Connected Enclosures on an Embedded Planar Graph
Christos Alexopoulos, School of Industrial and Systems Engineering,
Georgia Institute of Technology
J. Scott Provan, Department of Operations Research, University
of North Carolina
H. Donald Ratliff, School of Industrial and Systems Engineering,
Georgia Institute of Technology
Bryan R. Stutzman, CAPS Logistics
Abstract
We study five problems of finding minimal enclosures comprised of elements
of a connected, planar graph with a plane embedding. The first three problems
consider the identification of a shortest enclosing walk, cycle or trail
surrounding a polygonal, simply connected obstacle on the plane. We propose
polynomial algorithms that improve on existing algorithms. The last two
problems consider the formation of minimal zones (sets of adjacent regions
such that any pair of points in a zone can be connected by a non-zero width
curve that lies entirely in the zone). Specifically, we assume that
the regions of the graph have nonnegative weights and seek the formation
of minimum weight zones containing a set of points or a set of regions.
We prove that the last two problems are NP-hard and transform them to Steiner
arborescence/fixed-charge flow problems.