Let $P$ be a set of $n$ points in the plane. The
geometric minimum-diameter spanning tree (MDST) of
$P$ is a tree that spans $P$ and minimizes the
Euclidian length of the longest path. It is known
that there is always a mono- or a dipolar MDST,
i.e.\ a MDST with one or two nodes of degree greater
1, respectively. The more difficult dipolar case can
so far only be solved in slightly subcubic
time. This paper has two aims. First, we
present a solution to a new data structure for
facility location, the minimum-sum dipolar spanning
tree (MSST), that mediates between the
minimum-diameter dipolar spanning tree and the
discrete two-center problem (2CP) in the following
sense: find two centers $p$ and $q$ in $P$ that
minimize the sum of their distance plus the distance
of any other point (client) to the closer
center. This is of interest if the two centers do
not only serve their customers (as in the case of
the 2CP), but frequently have to exchange goods or
personnel between themselves. We give an $O(n^2 łog
n)$-time algorithm for this problem. A slight
modification of our algorithm yields a factor-4/3
approximation of the MDST. Second, we give two
fast approximation schemes for the MDST, i.e.\
factor-($1+\varepsilon$) approximation
algorithms. One uses a grid and takes
$O^*(E^6-1/3+n)$ time, where $E=1/\varepsilon$ and
the $O^*$-notation hides terms of type
$O(łog^O(1) E)$. The other uses the
well-separated pair decomposition and takes $O(n E^3
+ E n n)$ time. A combination of the two
approaches runs in $O^*(E^5 + n)$ time. Both schemes
can also be applied to MSST and 2CP.
%0 Journal Article
%1 ghpsw-flgmd-04
%A Gudmundsson, Joachim
%A Haverkort, Herman
%A Park, Sang-Min
%A Shin, Chan-Su
%A Wolff, Alexander
%D 2004
%J Computational Geometry: Theory and Applications
%K approximation_algorithm data_structure facility_location myown network_construction spanning_tree
%N 1
%P 87--106
%R 10.1016/j.comgeo.2003.07.007
%T Facility Location and the Geometric Minimum-Diameter
Spanning Tree
%V 27
%X Let $P$ be a set of $n$ points in the plane. The
geometric minimum-diameter spanning tree (MDST) of
$P$ is a tree that spans $P$ and minimizes the
Euclidian length of the longest path. It is known
that there is always a mono- or a dipolar MDST,
i.e.\ a MDST with one or two nodes of degree greater
1, respectively. The more difficult dipolar case can
so far only be solved in slightly subcubic
time. This paper has two aims. First, we
present a solution to a new data structure for
facility location, the minimum-sum dipolar spanning
tree (MSST), that mediates between the
minimum-diameter dipolar spanning tree and the
discrete two-center problem (2CP) in the following
sense: find two centers $p$ and $q$ in $P$ that
minimize the sum of their distance plus the distance
of any other point (client) to the closer
center. This is of interest if the two centers do
not only serve their customers (as in the case of
the 2CP), but frequently have to exchange goods or
personnel between themselves. We give an $O(n^2 łog
n)$-time algorithm for this problem. A slight
modification of our algorithm yields a factor-4/3
approximation of the MDST. Second, we give two
fast approximation schemes for the MDST, i.e.\
factor-($1+\varepsilon$) approximation
algorithms. One uses a grid and takes
$O^*(E^6-1/3+n)$ time, where $E=1/\varepsilon$ and
the $O^*$-notation hides terms of type
$O(łog^O(1) E)$. The other uses the
well-separated pair decomposition and takes $O(n E^3
+ E n n)$ time. A combination of the two
approaches runs in $O^*(E^5 + n)$ time. Both schemes
can also be applied to MSST and 2CP.
@article{ghpsw-flgmd-04,
abstract = {Let $P$ be a set of $n$ points in the plane. The
geometric minimum-diameter spanning tree (MDST) of
$P$ is a tree that spans $P$ and minimizes the
Euclidian length of the longest path. It is known
that there is always a mono- or a dipolar MDST,
i.e.\ a MDST with one or two nodes of degree greater
1, respectively. The more difficult dipolar case can
so far only be solved in slightly subcubic
time. \par This paper has two aims. First, we
present a solution to a new data structure for
facility location, the minimum-sum dipolar spanning
tree (MSST), that mediates between the
minimum-diameter dipolar spanning tree and the
discrete two-center problem (2CP) in the following
sense: find two centers $p$ and $q$ in $P$ that
minimize the sum of their distance plus the distance
of any other point (client) to the closer
center. This is of interest if the two centers do
not only serve their customers (as in the case of
the 2CP), but frequently have to exchange goods or
personnel between themselves. We give an $O(n^2 \log
n)$-time algorithm for this problem. A slight
modification of our algorithm yields a factor-4/3
approximation of the MDST. \par Second, we give two
fast approximation schemes for the MDST, i.e.\
factor-($1+\varepsilon$) approximation
algorithms. One uses a grid and takes
$O^*(E^{6-1/3}+n)$ time, where $E=1/\varepsilon$ and
the $O^*$-notation hides terms of type
$O(\log^{O(1)} E)$. The other uses the
well-separated pair decomposition and takes $O(n E^3
+ E n \log n)$ time. A combination of the two
approaches runs in $O^*(E^5 + n)$ time. Both schemes
can also be applied to MSST and 2CP.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Gudmundsson, Joachim and Haverkort, Herman and Park, Sang-Min and Shin, Chan-Su and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/21810ffbef3eeb59c59885bc8f52bd910/awolff},
cites = {am-dhsrr-95, asw-d2cp-98, bh-eamvb-99, c-adwse-00,
c-somgo-02, ck-dmpsa-95, clr-ia-90, gj-cigtn-79,
hlcw-mdstr-91, ht-mdstp-95, skbss-c1eag-03, ZZZ},
doi = {10.1016/j.comgeo.2003.07.007},
interhash = {f80c73e52b3f0579768ecef1e85f40dd},
intrahash = {1810ffbef3eeb59c59885bc8f52bd910},
journal = {Computational Geometry: Theory and Applications},
keywords = {approximation_algorithm data_structure facility_location myown network_construction spanning_tree},
number = 1,
pages = {87--106},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/ghpsw-flgmd-04.pdf},
succeeds = {ghpsw-flgmd-02},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Facility Location and the Geometric Minimum-Diameter
Spanning Tree},
volume = 27,
year = 2004
}