Voronoi diagram | EPFL Graph Search

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation. The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons. Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art. The simplest case In the simplest case, shown in the first picture, we are given a finite set of points {p1, ..., pn}

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem of finding an optimal solution for an integer program is known as integer programming. Integer programming is NP-hard in general, though several algorithms exist: Lenstra provided an algorithm that is polynomial if the dimension

n

is fixed. For variable dimension, the best known algorithm depends linearly on

n

, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix

A

. The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of

A

. A typical example for these integer programs are

N

-fold IPs, used for scheduling and social choice problems. We obtain the currently fastest fixed-parameter tractable algorithm with parameters tree-depth and the largest absolute value of the entries in

A

. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that

N

-fold integer programs of constant block size can be solved in strongly polynomial time. Assuming the exponential time hypothesis, we complement these results with a lower bound on the parameter dependency that almost matches the parameter dependency of the running time. As a consequence, we provide the currently strongest lower bound for

N

-fold integer programs. Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of

\R^n

. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell

\vc

of a lattice

\Lambda \subseteq \R^n

, which is the set of all points for which

0

is a closest lattice point. It is a polytope whose facets are induced by a set of lattice vectors, the Voronoi relevant vectors. A generic lattice has exponentially many Voronoi relevant vectors, leading to exponential space for certain CVP algorithms. In the second part of this thesis, we introduce the notion of a

c

-compact lattice basis

B \in \R^{n \times n}

that facilitates to represent the Voronoi relevant vectors with coefficients bounded by

c

. Such a basis allows to reduce the space requirement of Micciancio's & Voulgaris' algorithm for the closest vector problem from exponential to polynomial, while the running time becomes exponential in

c

. We show that for every lattice an

n^2

-compact basis exists, but there are lattices for which we cannot choose

c \in o (n)

. If the Voronoi cell is a zonotope, we can choose

c=1

, providing a single-exponential time and polynomial space algorithm for CVP, assuming a

1

-compact basis is known. Deciding whether a given lattice has a certain structure that helps to solve the closest vector problem more efficiently is a reappearing and non-trivial problem. The third part of this thesis is concerned with the specific structure of having an orthonormal basis. We show that this problem belongs to NP

\cap

co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.

EPFL2020

Quadratic serendipity element shape functions on general planar polygons

Juan Cao, Xiaodong Wei

This paper proposes a method for the construction of quadratic serendipity element (QSE) shape functions on planar convex and concave polygons. Existing approaches for constructing QSE shape functions are linear combinations of the pair-wise products of generalized barycentric coordinates with linear precision, restricted to the convex polygonal domain or resort to numerical optimization. We extend the construction to general polygons with no more than three collinear consecutive vertices. This is done by defining coefficients of the linear combination as the oriented area of triangles with vertices from the polygonal domain, which can be either convex or concave. The proposed shape functions possess linear to quadratic precision. We prove the interpolation error estimates for mean value coordinate-based QSE shape functions on convex and concave polygonal domains satisfying a set of geometric constraints for standard finite element analysis. We also tailor a polygonal mesh generation scheme that improves the uniformity and avoids short edges of Voronoi diagrams for their use in the QSE-based polygonal finite element computation. Numerical tests for the 2D Poisson equations on various domains are presented, demonstrating the optimal convergence rates in both the L-2-norm and the H-1-seminorm. 2022 Elsevier B.V. All rights reserved.

ELSEVIER SCIENCE SA2022

On compact representations of Voronoi cells of lattices

Christoph Hunkenschröder, Matthias Schymura

In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by c in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on c. Thus, our main focus is the behavior of the smallest possible value of c, with the following results: there always exist c-compact bases, where c is bounded by n(2) for an n-dimensional lattice; there are lattices not admitting a c-compact basis with c growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a 1-compact basis.

SPRINGER HEIDELBERG2020