# A polynomial time algorithm for solving the closest vector problem in zonotopal lattices

arXiv: https://arxiv.org/abs/2004.07574 · HTML: https://mlsanity.com/paper/2004.07574/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [CLEARMIND: Closed-Form Laplacian Embeddings of Arakelov-Green Resistance for Morphological Intrinsic Neuronal Distances](https://mlsanity.com/paper/2608.04460/) (2026)

## Abstract (arXiv)

In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e. a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type A. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.