Closest point search in lattices
Chalmers University of Technology · University of California, San Diego
Abstract
In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner (1995) variation of the Pohst (1981) method, is implemented. Given an arbitrary point x /spl isin/ /spl Ropf//sup m/ and a generator matrix for a lattice /spl Lambda/, the algorithm computes the point of /spl Lambda/ that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan (1983, 1987) algorithm…
Citation impact
- FWCI
- 62.67
- Percentile
- 100%
- References
- 88
Authors
4Topics & keywords
- Voronoi diagram
- Algorithm
- Mathematics
- Lattice problem
- Point (geometry)
- Search algorithm
- Combinatorics
- Lambda