Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
An Optimal Algorithm for Computing Angle-Constrained Spanners
verfasst von : Paz Carmi, Michiel Smid
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
S
be a set of
n
points in ℝ
d
. A graph
G
= (
S
,
E
) is called a
t
-spanner for
S
, if for any two points
p
and
q
in
S
, the shortest-path distance in
G
between
p
and
q
is at most
t
|
pq
|, where |
pq
| denotes the Euclidean distance between
p
and
q
. The graph
G
is called
θ
-angle-constrained, if any two distinct edges sharing an endpoint make an angle of at least
θ
. It is shown that, for any
θ
with 0 <
θ
<
π
/3, a
θ
-angle-constrained
t
-spanner can be computed in
O
(
n
log
n
) time, where
t
depends only on
θ
.