Let
be a rectangle that is decomposed into subrectangles. A
corridor of
is a tree
whose edges
belong to
,
where
has a vertex in the outer boundary and in each of the subrectangles in
. A
minimum-length corridor (MLC) is a corridor with the smallest length sum over its
edges. In this paper, we determine the minimum-length corridor of the rectangles
that are subdivided by horizontal and vertical lines into smaller rectangles
(grids) when all horizontal (or vertical) line segments have the same length
and the rest of the line segments have a length of at least
.
We also determine an upper bound for the minimum-length corridor of the
grids when all horizontal (or vertical) line segments have the same length
and the rest of line segments have length at most
. We
conclude with a conjecture that the upper bound is tight for some cases.
Keywords
trees, geometric aspects of graph theory, applications of
graph theory, tiling