Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Closest Periodic Vectors in L p Spaces
verfasst von : Amihood Amir, Estrella Eisenberg, Avivit Levy, Noa Lewenstein
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
The problem of finding the period of a vector
V
is central to many applications. Let
V
′ be a periodic vector closest to
V
under some metric. We seek this
V
′, or more precisely we seek the smallest period that generates
V
′. In this paper we consider the problem of finding the closest periodic vector in
L
p
spaces. The measures of “closeness” that we consider are the metrics in the different
L
p
spaces. Specifically, we consider the
L
1
,
L
2
and
L
∞
metrics. In particular, for a given
n
-dimensional vector
V
, we develop
O
(
n
2
) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic
n
-dimensional vector
V
′. We call that vector the
closest periodic vector
of
V
under the appropriate metric. We also show (three)
O
(
n
log
n
) time constant approximation algorithms for the (appropriate) period of the closest periodic vector.