Advertisement
Published in:
2011 | OriginalPaper | Chapter
Closest Periodic Vectors in L p Spaces
Authors : Amihood Amir, Estrella Eisenberg, Avivit Levy, Noa Lewenstein
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.