2014/05/27 by Robby G. McKilliam, Alex Grant, McKilliam, Robby G. +3
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Data Management and Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Slime Mold and Myxomycetes Research #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1405.7014
arxiv created 2014/05/27 · openalex publication_date 2014/05/27 · arxiv updated 2014/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for those lattices of Voronoi's first kind with known obtuse superbasis, a closest lattice point can be computed in O(n4) operations where n is the dimension of the lattice. To achieve this a series of relevant lattice vectors that converges to a closest lattice point is found. We show that the series converges after at most n terms. Each vector in the series can be efficiently computed in O(n3) operations using an algorithm to compute a minimum cut in an undirected flow network.