On Lattice Diameter Segments and A Discrete Borsuk Partition Problem Anouk E. Brose, Jesús A. De Loera, Gyivan Lopez-Campos, Antonio J. Torres Abstract The lattice diameter of a bounded set S ⊂ ℝ d S\subset\mathbb{R}^{d} measures the maximal number of lattice points in a segment whose endpoints are lattice points in S S . Such a segment is called a lattice diameter segment of S S . This simple invariant yields interesting applications and challenges. We describe a polynomial-time algorithm that computes lattice diameter segments of lattice polygons and show that computing lattice diameters of semi-algebraic sets in dimensions three and higher is 𝖭𝖯 \NP -hard. We prove that the function that counts lattice diameter segments in dilations of a lattice polygon is eventually a quasi-polynomial in the dilation factor. We also study the number of directions that lattice diameter segments can have. Finally, we prove a Borsuk-type theorem on the number of parts needed to partition a set of lattice points such that each part has strictly smaller lattice diameter . 0 0 footnotetext: Mathematics Subject Classification. 52A38, 52B20, 52B55, 52C07, 52C17, 68W35. 0 0 footnotetext: Key words and phrases. lattice diameter; lattice lines; lattice segments; lattice polygons; Ehrhart theory; computational complexity; Borsuk’s partition problem. 1 Introduction We study a fundamental geometric invariant of compact sets, called the lattice diameter , with a variety of applications in discrete geometry, integer optimization, and the geometry of numbers. We are not the first to study lattice diameters. This notion was introduced by Corzatt and Stolarsky [ Cor74 ] , studied by Alarcon [ AI87 ] and later by Bárány and Füredi [ BF01 ] . Here are the key definitions of this paper: Definition 1.1 . For a compact set S\subset\mathbb{R}^{d} , define \ldiam(S):=\max_{\mathbf{x},\mathbf{y}\in S\cap\mathbb{Z}^{d}}|\conv(\{\mathbf{x},\mathbf{y}\})\cap\mathbb{Z}^{d}|-1 as the lattice diameter of S . If \mathbf{x} and \mathbf{y} maximize \ldiam(S) , we call \conv(\{\mathbf{x},\mathbf{y}\}) a lattice diameter segment . Similarly, \aff(\{\mathbf{x},\mathbf{y}\}) is a lattice diameter line , and finally, \mathbf{y}-\mathbf{x} or any of its non-zero multiples is called a lattice diameter direction . Our paper investigates properties of lattice diameter segments and algorithms to compute them. Note that the lattice diameter of S and \conv(S) can differ when S is non-convex. When S is a convex body, then a lattice diameter line is an affine lattice line L such that |L\cap S\cap\mathbb{Z}^{d}| is maximal among all affine lattice lines. In this case the lattice diameter of S coincides with the lattice diameter of \conv(\{S\cap\mathbb{Z}^{d}\}) , a lattice polytope, thus we focus on studying lattice diameters of lattice polytopes. The Euclidean diameters and lattice diameters of lattice polytopes need not correlate. For fixed lattice diameter, the Euclidean diameter can be arbitrarily large ( Figure 1(a) ). Moreover, Euclidean diameter lines always pass through vertices [ GK92 , Lemma 1.7] , while lattice diameter lines may not ( Figure 1(b) ). (0,0) (\ell,0) (-n,-1) (\ell+n,1) (a) Lattice polygons with fixed lattice diameter (orange) and unbounded Euclidean diameter (green). (b) A lattice diameter segment contained in the interior of a lattice polygon. Figure 1 : Examples of lattice diameter segments in lattice polygons. Lattice lines and lattice diameter lines have several interesting connections. For example, in discrete tomography Gardner and Gritzmann have studied the reconstruction of lattice point sets from “ X -rays”, i.e., the collection of line sums over parallel lattice lines [ GG97 ] . Algorithmic connections to combinatorial optimization also exist through the notion of lattice width , which is used in algorithms for integer programming. The lattice width has been shown to be bounded by the lattice diameter [ BF01 ] . Motivated by questions in the geometry of numbers, the volumes of sections and projections of convex bodies have been studied for many years; see the surveys [ GKZ23 , NT23 ] . Analogous questions for the number of lattice points have only been studied more recently [ GGZ05 , FH22 , FH24 ] . Algorithmically, it is a challenge to determine a section of a convex body with maximal volume, but algorithms exist for convex polytopes [ BDLM25 ] . However, computing a section of a lattice polytope with the most lattice points is still an open problem. In the plane, this problem reduces to finding a lattice diameter segment, which we solve here. Furthermore, classifications of convex lattice polytopes have been studied with respect to different invariants. This is of particular interest in algebraic geometry, where reflexive polytopes correspond to specific toric Fano varieties that have ties to mirror symmetry in physics [ Bat99 , Kas06 ] . Arnold, Bárány, Pach, Vershik, and others [ Arn80 , BP92 , BV92 ] have classified lattice polytopes by their volume while Averkov, Lagarias, Nill, Weismantel, Ziegler, and others [ LZ91 , AWW11 , NZ11 ] have continued the classification, based on the number of interior lattice points. We stress that classifying lattice polytopes by their lattice diameter is also possible. A simple result by S. Rabinowitz [ Rab89 ] shows that if \ldiam(P)2014 . Today, there are known counterexamples in dimensions 64 and higher, see [ JB14 ] , but the problem is still open for 4\leq d\leq 63 . More generally, the problem of partitioning a set into sets with smaller diameter is studied for specific classes of bounded sets. In this paper, we study this problem for sets of lattice points with respect to the lattice diameter instead of the Euclidean diameter. We refer to this challenge as the discrete Borsuk partition problem . Our Contributions In Section 2.1 we show that lattice diameter lines of lattice polygons can be computed efficiently: Theorem 2.4. Let P\subset\mathbb{R}^{2} be a lattice polygon. There exists a polynomial-time algorithm that computes a lattice diameter line of P in every direction in which such a line exists. In particular, the lattice diameter of P can be computed in polynomial time. In contrast, we show the following hardness result in Section 2.2 : Theorem 2.7. Let d\geq 3 and let K\subset\mathbb{R}^{d} be a d -dimensional bounded semi-algebraic set. Computing a lattice diameter of K is an \NP -hard problem. In Section 3 we generalize Ehrhart theory to counting the set of lattice diameter lines. While counting the number of lattice lines in a fixed direction that intersect P in a lattice point is not hard [ Bro ] , counting those that are lattice diameter lines is much more difficult. Surprisingly, we have an Ehrhart-type result. Definition 1.2 . For a lattice polytope P , let \LD_{P}(k) denote the number of lattice diameter lines of the dilated polytope kP . Theorem 3.6. Let P\subset\mathbb{R}^{2} be a lattice polygon. There exists a positive integer q such that \LD_{P}:\mathbb{N}_{\geq q}\to\mathbb{N} agrees with a quasi-polynomial function of degree one whose period divides q . In Section 4 we begin by generalizing two results by Alarcon [ AI87 ] to higher dimensions. The first result bounds the total number of lattice diameter directions: Theorem 4.3. Let P\subset\mathbb{R}^{d} be a lattice d -polytope with \ldiam(P)=1 . Then P has at most \binom{2^{d}}{2} lattice diameter directions and this bound is best possible. The second generalization is about a local property of lattice diameter segments. In fact, we prove it more generally for bounded sets. This result is a key ingredient to prove the discrete version of Borsuk’s partition problem. Lemma 4.6. Let S\subset\mathbb{Z}^{d} be a bounded set and let \mathbf{x}\in S . Then, the number of lattice diameter segments of S that have \mathbf{x} as an endpoint is bounded by 2^{d}-1 , and this bound is best possible. To study the discrete version of Borsuk’s partition problem, we define the following notion: Definition 1.3 . Let S\subset\mathbb{Z}^{d} be a bounded set. Define the lattice Borsuk number of S , \beta_{\mathbb{Z}}(S) , as the minimal size of a partition of S where each part has a smaller lattice diameter than \ldiam(S) . Finally, the following theorem answers the discrete version of Borsuk’s partition problem: Theorem 4.8. Let S\subset\mathbb{Z}^{d} be a bounded set. Then, \beta_{\mathbb{Z}}(S)\leq 2^{d} and this bound is best possible. In particular, Theorem 4.8 says that \beta_{\mathbb{Z}}(P\cap\mathbb{Z}^{d})\leq 2^{d} for d -dimensional polytopes P . Note that we are not partitioning P into smaller polytopes, i.e., the parts of P\cap\mathbb{Z}^{d} are not necessarily the lattice points of a polytope. The bound 2^{d} is also best possible for polytopes; it is attained for the lattice points of a d -dimensional cube. Notation We use basic notions and notation as can be found in the textbooks [ Gru07 , Zie12 ] . A d -polytope P is the convex hull of finitely many points in \mathbb{R}^{d} whose affine hull is d -dimensional. It is called a lattice (or rational ) d -polytope if its vertices belong to the integer lattice \mathbb{Z}^{d} (or to \mathbb{Q}^{d}) . We say two lattice d -polytopes P and Q are unimodularly equivalent if there exists a unimodular matrix A\in\GL(d,\mathbb{Z}) and \mathbf{t}\in\mathbb{Z}^{d} such that P=AQ+\mathbf{t} , i.e., these transformations correspond to lattice preserving maps. We write \spn(S),\,\aff(S) , and \conv(S) for the linear, affine, and convex hull of a set S\subset\mathbb{R}^{d} , respectively. The segment between two points \mathbf{x},\mathbf{y}\in\mathbb{R}^{d} is denoted [\mathbf{x},\mathbf{y}]:=\conv(\{\mathbf{x},\mathbf{y}\}) and when \mathbf{x},\mathbf{y}\in\mathbb{Z}^{d} , we call this a lattice segment . A line will always mean an affine line and a lattice line is a line that passes through at least two lattice points. We say that a line has direction \mathbf{u} if it can be written as \mathbf{x}+\spn(\mathbf{u}) for some \mathbf{x}\in\mathbb{R}^{d} . We say \mathbf{u} -lattice line (or segment) if the lattice line (or segment) has direction \mathbf{u} . Furthermore, from now on a diameter direction means a lattice diameter direction. The inner product we use is the standard inner product on \mathbb{R}^{d} , denoted \langle\cdot,\cdot\rangle . A hyperplane and its closed half-spaces are denoted H(\mathbf{a},\alpha):=\{\mathbf{x}\in\mathbb{R}^{d}\,\mathrm{:}\,\langle\mathbf{a},\mathbf{x}\rangle=\alpha\} , H^{+}(\mathbf{a},\alpha) and H^{-}(\mathbf{a},\alpha) , respectively. For a Lebesgue measurable set S\subset\mathbb{R}^{d} , we write \vol(S) which means the intrinsic volume of S in \aff(S) . Furthermore, a vector \mathbf{u}=(u_{1},\ldots,u_{d})\in\mathbb{Z}^{d} is called primitive if \gcd(u_{1},\ldots,u_{d})=1 . For a positive integer n we write [n]:=\{1,\ldots,n\} and \binom{[n]}{k} denotes the k -element subsets of [n] . For integers a,q\in\mathbb{Z} we write a\bmod q to mean the representative of a in \{0,\ldots,q-1\} . In Section 4 , we use graph theory and standard notation as in [ BM08 ] . A graph is a simple undirected graph G=(V,E) , where V is a finite set and E\subseteq\binom{V}{2} . In this context, V or V(G) is the set of vertices and E or E(G) is the set of edges of the graph G . Two vertices u,v\in V are called adjacent if \{u,v\}\in E . 2 Computing lattice diameters and lattice diameter lines In this section we will explain and prove Theorem 2.4 and Theorem 2.7 . 2.1 A polynomial-time algorithm to compute lattice diameter lines in the plane Let P be a lattice polygon. We present an algorithm that runs in polynomial time in the input size of P and computes a lattice diameter line of P for every direction in which one exists. The algorithm relies on the following three claims: • For every diameter direction \mathbf{u} , there exists a lattice diameter line in direction \mathbf{u} passing through a vertex \mathbf{v} and an edge e such that some translate of \aff(e) is tangent to P at \mathbf{v} . In this case, we say that \mathbf{v} is an opposite vertex to the edge e . • For every pair (e,\mathbf{v}) , where e is an edge and \mathbf{v} is an opposite vertex to e , one can compute in polynomial time a local lattice diameter line at \mathbf{v} of the triangle \conv\{e,\mathbf{v}\} , i.e., a line through \mathbf{v} that intersects \conv(\{e,\mathbf{v}\}) in the most lattice points. • At most three lattice diameter lines pass through any fixed vertex. This was proven by Alarcon [ AI87 , Lemma 2.4] (and it also follows from our Lemma 4.6 ). The algorithm is as follows: Algorithm 1 Computing Lattice Diameter Lines Input: a lattice polygon P given by its vertices Output: at least one lattice diameter line for each direction in which a lattice diameter line exists 1: Initialize two empty sets: \mathcal{T} for triangles, and \mathcal{L} for candidate lines 2: for all edges e of P do 3: compute all opposite vertices \mathbf{v} to e (each edge has at most two opposite vertices) 4: form triangles \conv(\{e,\mathbf{v}\}) and add them to \mathcal{T} 5: end for 6: for all triangles in \mathcal{T} do 7: compute up to three local lattice diameter lines of T=\conv(\{e,\mathbf{v}\}) at \mathbf{v} 8: add these local lattice diameter lines to \mathcal{L} 9: end for 10: return all lines in L\in\mathcal{L} that maximize |L\cap P\cap\mathbb{Z}^{2}| We proceed to prove some lemmas. Recall that for a primitive vector \mathbf{u}\in\mathbb{Z}^{d}\setminus\{0\} , and a \mathbf{u} -lattice line L , the lattice normalized length of the segment L\cap P is \nvol(L\cap P):=\frac{\vol(L\cap P)}{\|\mathbf{u}\|} . Lemma 2.1 . Let P be a lattice polytope and L be a line that intersects P . Then \displaystyle\left\lfloor\nvol(L\cap P)\right\rfloor\leq|L\cap P\cap\mathbb{Z}^{d}|\leq\left\lfloor\nvol(L\cap P)\right\rfloor+1 and the upper bound is attained if L contains a lattice point on the boundary of P . Proof. Parametrize the line as L=\{\mathbf{x}_{0}+t\mathbf{u}:t\in\mathbb{R}\} , where \mathbf{x}_{0} is an arbitrary lattice point on L and \mathbf{u}\in\mathbb{Z}^{d} is a primitive vector in the direction of L . Then, the intersection L\cap P is a segment with endpoints \mathbf{a}=\mathbf{x}_{0}+t_{1}\mathbf{u} and \mathbf{b}=\mathbf{x}_{0}+t_{2}\mathbf{u} , for some real numbers t_{1}\leq t_{2} . The lattice points in L\cap P are precisely those points of the form \mathbf{x}_{0}+k\mathbf{u} with k\in\mathbb{Z}\cap[t_{1},t_{2}] . Moreover, \nvol(L\cap P)=\frac{\|\mathbf{b}-\mathbf{a}\|}{\|\mathbf{u}\|}=\frac{\|(t_{2}-t_{1})\mathbf{u}\|}{\|\mathbf{u}\|}=|t_{2}-t_{1}|=t_{2}-t_{1}. If t_{1} is not an integer, then |L\cap P\cap\mathbb{Z}^{d}|=\lfloor t_{2}\rfloor-\lceil t_{1}\rceil+1=\lfloor t_{2}\rfloor-\lfloor t_{1}\rfloor and the claim follows from the observation \lfloor t_{2}-t_{1}\rfloor\leq\lfloor t_{2}\rfloor-\lfloor t_{1}\rfloor\leq\lfloor t_{2}-t_{1}\rfloor+1 . If at least one of t_{1} or t_{2} is an integer, then |L\cap P\cap\mathbb{Z}^{d}|=\lfloor t_{2}\rfloor-\lceil t_{1}\rceil+1=\lfloor t_{2}-t_{1}\rfloor+1=\lfloor\nvol(L\cap P)\rfloor+1 . ∎ As mentioned above, we say that a vertex \mathbf{v} of a lattice polygon P is an opposite vertex to an edge e of P if the furthest translate of \aff(e) that intersects P passes through \mathbf{v} . More formally, if \mathbf{a} is an outward normal vector of the edge e , then \langle\mathbf{a},\mathbf{v}\rangle=\min_{\mathbf{x}\in P}\langle\mathbf{a},\mathbf{x}\rangle . See Figure 2 . \mathbf{a} (0,0) \mathbf{v} L\cap P \footnotesize\text{edge }e opposite vertex H(\mathbf{a},\langle\mathbf{a},\mathbf{v}\rangle) \footnotesize\aff(e) Figure 2 : A lattice diameter line passing through an edge and its opposite vertex. If \mathbf{u}\in\mathbb{Z}^{2}\setminus\{0\} , then we call a \mathbf{u} -lattice line L a \mathbf{u} -lattice diameter line of P , if among all lines in direction \mathbf{u} , it contains the most lattice points in P . The following lemma shows that a \mathbf{u} -lattice diameter line of P can always be chosen to pass through an edge of P and an opposite vertex. This follows from [ BF01 , Lemma 1] , where it is stated without a proof. We include one here for completeness. Lemma 2.2 . [ BF01 , Lemma 1] Let P be a lattice polygon and \mathbf{u}\in\mathbb{Z}^{2}\setminus\{0\} . There exists a \mathbf{u} -lattice diameter line L that passes through a vertex \mathbf{v} of P and through an edge e of P with outward normal vector \mathbf{a} such that \langle\mathbf{a},\mathbf{v}\rangle=\min_{\mathbf{x}\in P}\langle\mathbf{a},\mathbf{x}\rangle . Proof. Lemma 2.1 implies that if a \mathbf{u} -lattice line L passes through a vertex of P , and satisfies \vol(L\cap P)\geq\vol(L^{\prime}\cap P) for all \mathbf{u} -lattice lines L^{\prime} , then L is a \mathbf{u} -lattice diameter line of P . First we prove that such a line exists. Let L be any line in direction \mathbf{u} satisfying \vol(L\cap P)\geq\vol(L^{\prime}\cap P) for all lines L^{\prime} in direction \mathbf{u} (by compactness of P such a line exists). If L passes through parallel edges, then a translate of L along \mathbf{u}^{\perp} will pass through a vertex of P and its intersection with P will have the same length. Else, translating L in one direction along \mathbf{u}^{\perp} , until it passes through a vertex, will strictly increase the length of its intersection with P , a contradiction. This proves the existence of such a line, and necessarily, it will be a \mathbf{u} -lattice line. So let L be a \mathbf{u} -lattice line that passes through some vertex of P and satisfies \vol(L\cap P)\geq\vol(L^{\prime}\cap P) for all \mathbf{u} -lattice lines L^{\prime} . First, suppose that L passes through the relative interior of an edge e and through a vertex \mathbf{v} of P . Towards a contradiction, suppose \langle\mathbf{a},\mathbf{v}\rangle\neq\min_{\mathbf{x}\in P}\langle\mathbf{a},\mathbf{x}\rangle . Let \tilde{\mathbf{v}} be a vertex for which \min_{\mathbf{x}\in P}\langle\mathbf{a},\mathbf{x}\rangle is attained. It is an elementary trigonometry calculation to show that there exists a point \mathbf{p}\in[\mathbf{v},\tilde{\mathbf{v}}]\subseteq P such that a translate of L passing through \mathbf{p} also passes through e , and its intersection with P is longer. For the second case, suppose L passes through two vertices \mathbf{v} and \mathbf{w} . Using convexity of P and the fact that L\cap P is the longest segment in P in direction \mathbf{u} one can find parallel supporting hyperplanes (lines) of P at \mathbf{v} and at \mathbf{w} . Rotating them, until one of the lines becomes tangent to an edge of P proves this case. ∎ Now consider all triangles T_{e}=\conv(\{e,\mathbf{v}_{e}\}) where e is an edge of P , and \mathbf{v}_{e} is an opposite vertex to e . Lemma 2.2 implies that for every diameter direction \mathbf{u} there exists a lattice diameter line that is a local lattice diameter line of T_{e} at \mathbf{v}_{e} for some edge e . Lemma 2.3 is the key ingredient to compute local lattice diameter lines of lattice triangles. Lemma 2.3 . Let T=\conv\{e,\mathbf{v}\} be a lattice triangle, where e is an edge of T with outward normal vector \mathbf{a} , and \mathbf{v} is its opposite vertex. If \mathbf{w}_{1},\mathbf{w}_{2}\in T\cap\mathbb{Z}^{2}\setminus\{\mathbf{v}\} satisfy \langle\mathbf{a},\mathbf{w}_{1}\rangle\leq\langle\mathbf{a},\mathbf{w}_{2}\rangle , then for L_{1}:=\aff(\{\mathbf{v},\mathbf{w}_{1}\}) and L_{2}:=\aff(\{\mathbf{v},\mathbf{w}_{2}\}) |L_{1}\cap T\cap\mathbb{Z}^{2}|\geq|L_{2}\cap T\cap\mathbb{Z}^{2}|. Proof. If \langle\mathbf{a},\mathbf{w}_{1}\rangle=\langle\mathbf{a},\mathbf{w}_{2}\rangle , then \mathbf{w}_{1} and \mathbf{w}_{2} lie on the same hyperplane H(\mathbf{a},\langle\mathbf{a},\mathbf{w}_{1}\rangle) , and by proportionality of lines \frac{\operatorname{vol}(L_{1}\cap T)}{\|\mathbf{w}_{1}-\mathbf{v}\|}=\frac{\operatorname{vol}(L_{2}\cap T)}{\|\mathbf{w}_{2}-\mathbf{v}\|}. Applying Lemma 2.1 , we obtain |L_{1}\cap T\cap\mathbb{Z}^{2}|=\left\lfloor\frac{\operatorname{vol}(L_{1}\cap T)}{\|\mathbf{w}_{1}-\mathbf{v}\|}\right\rfloor+1=\left\lfloor\frac{\operatorname{vol}(L_{2}\cap T)}{\|\mathbf{w}_{2}-\mathbf{v}\|}\right\rfloor+1=|L_{2}\cap T\cap\mathbb{Z}^{2}|. On the other hand, if \langle\mathbf{a},\mathbf{w}_{1}\rangle<\langle\mathbf{a},\mathbf{w}_{2}\rangle , then there exists a \mathbf{w}^{\prime}\in[\mathbf{v},\mathbf{w}_{2}] such that \langle\mathbf{a},\mathbf{w}^{\prime}\rangle=\langle\mathbf{a},\mathbf{w}_{1}\rangle . Again, by proportionality of lines \frac{\operatorname{vol}(L_{1}\cap T)}{\|\mathbf{w}_{1}-\mathbf{v}\|}=\frac{\operatorname{vol}(L_{1}\cap T)}{\|\mathbf{w}^{\prime}-\mathbf{v}\|}\geq\frac{\operatorname{vol}(L_{2}\cap T)}{\|\mathbf{w}_{2}-\mathbf{v}\|}. Applying Lemma 2.1 it follows that |L_{1}\cap T\cap\mathbb{Z}^{2}|\geq|L_{2}\cap T\cap\mathbb{Z}^{2}| . ∎ Using the lemmas above, we prove that the algorithm Computing Lattice Diameters is correct and runs in polynomial time in n and \log_{2}(c) , where n is the number of vertices of P and c is the largest absolute value of a coordinate of a vertex. Theorem 2.4 . Let P be a lattice polygon. There exists a polynomial-time algorithm that computes a lattice diameter line of P for every direction in which a lattice diameter line exists. In particular, the lattice diameter of P can be computed in polynomial time. Proof. Correctness of the algorithm: Let \mathbf{u} be a diameter direction of P . By Lemma 2.2 , there exists a lattice diameter line L in direction \mathbf{u} , that passes through an edge e and an opposite vertex \mathbf{v} to that edge. Thus L is a local lattice diameter line of T=\conv(\{e,\mathbf{v}\}) at \mathbf{v} . Let m=\min\{3,|T\cap\mathbb{Z}^{2}\setminus\{\mathbf{v}\}|\} , and let L_{i} for i\in[m] be the lattice lines computed in the second for loop . By Alarcon [ AI87 , Lemma 2.4] at most three lattice diameter lines pass through \mathbf{v} , thus L must be contained in \{L_{i}\,\mathrm{:}\,i\in[m]\} . Complexity of the algorithm: We can assume that the input data is a list of vertices, edges, and incidence relations between the vertices and edges, since in dimension two this data can be computed from the vertices of P in polynomial time. Let n denote the number of vertices of P . 1. first for loop: This loop is repeated n times, since P has n edges. Finding an opposite vertex \mathbf{v} to an edge e is linear optimization, which can be done in polynomial time in the input [ Sch86 ] . Further, checking if \mathbf{v} lies on an edge [\mathbf{v},\mathbf{v}^{\prime}] that is parallel to e , in which case e has two opposite vertices, can also be done in O(1) . Each edge contributes at most two triangles, so throughout the whole algorithm |\mathcal{T}|\leq 2n . 2. second for loop: This for loop is repeated |\mathcal{T}| times. For one iteration: Computing |T\cap\mathbb{Z}^{2}| can be computed in polynomial time, for example, by Pick’s Theorem [ Pic99 ] . Let \mathbf{a} be an outward normal vector of T with \min_{\mathbf{x}\in T}\langle\mathbf{a},\mathbf{x}\rangle=\langle\mathbf{a},\mathbf{v}\rangle . A lattice point \mathbf{w}_{1}\in T\cap\mathbb{Z}^{2}\setminus\{\mathbf{v}\} minimizes the functional \langle\mathbf{a},\cdot\rangle if and only if it minimizes this functional over the lattice points of the rational polygon T^{\prime}:=T\cap H^{-}(\mathbf{a},\langle\mathbf{a},\mathbf{v}\rangle+1). The other \mathbf{w}_{i} for i\in[m] can be computed similarly, with an additional check if \mathbf{w}_{i}\in T\cap H(\mathbf{a},\langle\mathbf{a},\mathbf{w}_{i-1}\rangle) . Since integer linear programming can be solved in polynomial time in dimension two [ EL03 ] , the minimizers \mathbf{w}_{i} can be computed in polynomial time in the input size of P . 3. The number of lattice points on a segment L\cap T , where L=\aff(\{\mathbf{v},\mathbf{w}\}) , is given by |L\cap T\cap\mathbb{Z}^{2}|=\left\lfloor\frac{\operatorname{vol}(L\cap T)}{\|\mathbf{w}-\mathbf{v}\|}\right\rfloor+1. |\mathcal{L}| is bounded above by 3\cdot(2n) and finding maximizers of |L\cap T\cap\mathbb{Z}^{2}| is linear in |\mathcal{L}| . ∎ Remark 2.5 . Lemma 2.3 extends to simplices in any dimension. Let S=\conv(\{F,\mathbf{v}\}) be a simplex where \mathbf{v} is an opposite vertex to a facet F . The argument from Theorem 2.4 and the fact that integer linear programming can be solved in polynomial time in fixed dimension [ Len83 ] yield a polynomial-time method to compute the local lattice diameter of S at \mathbf{v} . 2.2 Hardness of computing lattice diameters in dimensions three and higher A key ingredient in our algorithm to compute lattice diameters of lattice polygons is the existence of lattice diameter lines that pass through vertices. This fails in higher dimensions, as the following example shows. Example 2.6 . For \mathbf{v}_{1}=(-1,0),\,\mathbf{v}_{2}=(0,-1),\,\mathbf{v}_{3}=(1,1) , let P=\conv(\{(-m,\mathbf{v}_{1}),(-m,\mathbf{v}_{2}),(-m+1,\mathbf{v}_{3}),(m,-\mathbf{v}_{1}),(m,-\mathbf{v}_{2}),(m-1,-\mathbf{v}_{3})\}), where m\geq 2 . The unique lattice diameter segment of P is the segment on the first-coordinate axis, from values -(m-1) to m-1 . It does not pass through a vertex of P , not even through a lattice point on the boundary of P . Figure 3 depicts this polytope for m=3 with its lattice diameter segment in orange. Figure 3 : A unique lattice diameter segment contained in the interior of a lattice polytope. We show that in a general setting computing lattice diameters becomes \NP -hard. Theorem 2.7 . Let d\geq 3 and let K\subseteq\mathbb{R}^{d} be a d -dimensional bounded semi-algebraic set. Computing the lattice diameter of K is \NP -hard. Proof. For integers a,b,c>0 let f(x,y):=(x^{2}-a-by)^{2} and R(a,b,c):=\{(x,y)\,\mathrm{:}\,1\leq x\leq c-1,\frac{1-a}{b}\leq y\leq\frac{(c-1)^{2}-a}{b}\} . It was shown in [ DLHKW06 , Lemma 2.1] that deciding whether the minimum of f over R\cap\mathbb{Z}^{2} is zero, is \NP -hard. This is a polynomial-time reduction from the \NP -complete problem AN1 in [ GJ79 , p. 249] . We may assume that c>\max\{2,b\} (which can be checked in constant time), otherwise R\cap\mathbb{Z}^{2}=\emptyset . Under these assumptions R is also two-dimensional. We construct a three-dimensional semi-algebraic set K with description length polynomial in a,b,c , such that determining the lattice diameter of K corresponds to determining the minimum value of f on R\cap\mathbb{Z}^{2} . Construction of K : Let \mathbf{p}=(1,\lceil\frac{1-a}{b}\rceil)\in R\cap\mathbb{Z}^{2} , Z:=f(\mathbf{p})+\max\{\lfloor\frac{c^{2}-2c}{b}\rfloor+1,c-1\} , and define K:=\{(x,y,z)\,\mathrm{:}\,(x,y)\in R,\ f(x,y)\leq z\leq Z\}. K is bounded above by R\times\{Z\} and below by the graph of f . Figure 4 is a sketch of this. R\times\{Z\} R K Figure 4 : The construction given in the proof of Theorem 2.7 . The choice of Z ensures that a small region around the segment S_{\mathbf{p}}:=[(\mathbf{p},f(\mathbf{p})),(\mathbf{p},Z)] is contained in the interior of K , thus \dim K=3 . Furthermore, S_{\mathbf{p}} contains at least \max\{\lfloor\frac{c^{2}-2c}{b}\rfloor+1,c-1\}+1 lattice points. Any segment not in direction (0,0,1) projects to a segment in the x -axis, or y -axis, but the number of lattice points in the projection of K to these axes is bounded by c-1 , and \lfloor\frac{c^{2}-2c}{b}\rfloor+1 , respectively. Thus a lattice diameter line of K must have direction (0,0,1) . Then, for a lattice diameter line L of K \displaystyle|L\cap K\cap\mathbb{Z}^{3}|=Z-\min_{(x,y)\in R\cap\mathbb{Z}^{2}}f(x,y)+1. So |L\cap K\cap\mathbb{Z}^{3}|=Z-1 if and only if \min_{(x,y)\in R\cap\mathbb{Z}^{2}}f(x,y)=0 , which means that determining the lattice diameter of K is \NP -hard. For d\geq 3 consider K_{d}:=[0,1]^{d-3}\times K , which, as a Cartesian product of semi-algebraic sets, is a semi-algebraic set. Analogously, a lattice diameter line of K_{d} has direction (0,\ldots,0,1) , and determining whether the lattice diameter is Z-1 is \NP -hard, since it determines whether the minimum of f over R\cap\mathbb{Z}^{2} is zero. Lastly, note that K_{d} for d\geq 3 is defined by a single quartic polynomial, a constant inequality, which are both polynomial in a,b,c , and 2^{d-3} linear inequalities in 0 and 1 (for [0,1]^{d-3} ). Hence the description length of K and K_{d} are polynomial in the encoding length of a,b and c . ∎ Remark 2.8 . The construction of K is such that the lattice diameter is guaranteed to have direction (0,\ldots,0,1) . Thus we proved that computing a lattice diameter of a bounded semi-algebraic set, even in a fixed direction, is \NP -hard. Furthermore, we conjecture that this computation stays hard, even for lattice polytopes: Conjecture 1 . Let d\geq 3 and let P be a lattice d -polytope. Computing a lattice diameter of P is an \NP -hard problem. 3 Counting lattice diameter lines Ehrhart theory studies the number of lattice points in dilations of a given lattice (or rational) polytope. A fundamental result by Ehrhart states that this counting function agrees with a polynomial function for lattice polytopes, and a quasi-polynomial function for rational polytopes. For details, see [ BR15 ] . In this section we show that for lattice polygons P the counting function \LD_{P}(k) , which counts the number of lattice diameter lines (or segments) in the dilate kP , agrees with a quasi-polynomial function. Example 3.1 . Let P=\conv(\{(0,0),(1,3),(5,1),(6,4)\}) . In Figure 5 we depict the segments L\cap P for lattice diameter lines L of kP for k=1,\ldots,6 . P 2P 3P 4P 5P 6P Figure 5 : The pattern of lattice diameter lines repeats periodically under dilation of P . Then for all k\in\mathbb{N} we get \displaystyle\LD_{P}(k)=\begin{cases}2k+1&\text{if }k\equiv 1\pmod{3},\\ \frac{4}{3}k+\frac{4}{3}&\text{if }k\equiv 2\pmod{3},\\ \frac{2}{3}k+1&\text{if }k\equiv 0\pmod{3}.\end{cases} Indeed, \LD_{P}(1)=3,\ \LD_{P}(2)=4,\ \LD_{P}(3)=3,\ \LD_{P}(4)=9,\ \LD_{P}(5)=8 and \LD_{P}(6)=5 . For a set X\subseteq\mathbb{R}^{d} we write kX:=\{k\mathbf{x}\,\mathrm{:}\,\mathbf{x}\in X\} for the dilated set by k\in\mathbb{N} . In particular, for a polytope P , any line intersecting kP can be written as the dilated line kL for a line L intersecting P . Lemma 3.2 . Let P be a lattice polygon and let k\in\mathbb{N} . Then, a diameter direction of kP is also a diameter direction of P . Proof. Let \mathbf{u} be a diameter direction of kP and let kL be a lattice diameter line with direction \mathbf{u} that passes through a vertex of kP . (That is, L is a line that passes through the corresponding vertex of P ). Let L^{\prime} be a lattice line that passes through a vertex of P . Then, kL^{\prime} also passes through a vertex of kP and by Lemma 2.1 \displaystyle\lfloor\nvol(kL\cap kP)\rfloor+1=|kL\cap kP\cap\mathbb{Z}^{2}|\geq|kL^{\prime}\cap kP\cap\mathbb{Z}^{2}|=\lfloor\nvol(kL^{\prime}\cap kP)\rfloor+1. (1) The normalized volume is a homogeneous function in k , so ( 1 ) and Lemma 2.1 yield \displaystyle|L\cap P\cap\mathbb{Z}^{2}|=\lfloor\nvol(L\cap P)\rfloor+1\geq\lfloor\nvol(L^{\prime}\cap P)\rfloor+1=|L^{\prime}\cap P\cap\mathbb{Z}^{2}|. Since for every diameter direction of P there exists a lattice diameter line in that direction, that passes through a vertex, we proved that L is a lattice diameter line of P . In particular, \mathbf{u} is a diameter direction of P . ∎ The following lemma shows that under dilation of the polygon only certain lattice diameter lines remain, specifically those for which L\cap P has the largest normalized length. Figure 6 illustrates this phenomenon. Figure 6 : Lattice diameter segments can “disappear” when dilating a polygon. Lemma 3.3 . Let P be a lattice polygon. There exists a positive integer q such that for all k\geq q , and all lattice diameter lines kL,kL^{\prime} of kP , \nvol(L\cap P)=\nvol(L^{\prime}\cap P) . Proof. Let \mathcal{R} be the set of rational lines whose direction is a diameter direction of P . By Lemma 2.2 we can choose a lattice diameter line L\in\mathcal{R} such that \nvol(L\cap P)\geq\nvol(L^{\prime}\cap P) for all rational lines L^{\prime}\in\mathcal{R} . Let \nvol(L\cap P)=\frac{p}{q} for some p,q\in\mathbb{N} and note that \frac{p}{q}\geq 1 . Let kL^{\prime} be a lattice diameter line of kP . By Lemma 3.2 its direction is a diameter direction of P , so L^{\prime}\in\mathcal{R} . It suffices to show \nvol(L\cap P)\leq\nvol(L^{\prime}\cap P) , so that we obtain equality. Towards a contradiction, suppose \nvol(L\cap P)>\nvol(L^{\prime}\cap P) . The normalized volume is a homogeneous function in k , so \displaystyle\nvol(kL^{\prime}\cap kP)<\nvol(kL\cap kP)=p+\frac{(k-q)p}{q}. Together with Lemma 2.1 and using \frac{(k-q)p}{q}\geq 1 , this yields \displaystyle|kL^{\prime}\cap kP\cap\mathbb{Z}^{2}|\leq\lfloor\nvol(kL^{\prime}\cap kP)\rfloor+11 , then there exist parallel edges e_{1},e_{2} of P such that L\subseteq\conv(e_{1}\cup e_{2}) for all L\in\mathcal{L} . Proof. Let \mathbf{a}\in\mathbb{Z}^{2}\setminus\{0\} be orthogonal to \mathbf{u} and let \mathbf{v}_{1},\ldots,\mathbf{v}_{n} be the vertices of P , enumerated such that \langle\mathbf{a},\mathbf{v}_{i}\rangle\leq\langle\mathbf{a},\mathbf{v}_{i+1}\rangle for all i\in[n-1] . Define the parallel chambers C_{i}:=P\cap H^{+}(\mathbf{a},\langle\mathbf{a},\mathbf{v}_{i}\rangle)\cap H^{-}(\mathbf{a},\langle\mathbf{a},\mathbf{v}_{i+1}\rangle) for all i\in[n-1] for which \langle\mathbf{a},\mathbf{v}_{i}\rangle<\langle\mathbf{a},\mathbf{v}_{i+1}\rangle , so C_{i} is full-dimensional. A chamber C_{i} is bounded by H(\mathbf{a},\langle\mathbf{a},\mathbf{v}_{i}\rangle),\,H(\mathbf{a},\langle\mathbf{a},\mathbf{v}_{i+1}\rangle) , and two edges e_{i1},e_{i2} of P . If the edges e_{i1} and e_{i2} are parallel, then all segments C_{i}\cap H(\mathbf{a},b_{i}) for b_{i}\in[\langle\mathbf{a},\mathbf{v}_{i}\rangle,\langle\mathbf{a},\mathbf{v}_{i+1}\rangle] have the same length. Otherwise, there is a unique segment of the form C_{i}\cap H(\mathbf{a},b_{i}) where b_{i}\in[\langle\mathbf{a},\mathbf{v}_{i}\rangle,\langle\mathbf{a},\mathbf{v}_{i+1}\rangle] , which is the longest among all segments in this chamber. Note that P\cap H(\mathbf{a},b_{i})=C_{i}\cap H(\mathbf{a},b_{i}) , so if in the setting of this lemma |\mathcal{L}|>1 , then all L\cap P for L\in\mathcal{L} have the same length, and thus are contained in a chamber bounded by parallel edges. ∎ Finally, we count the number of \mathbf{u} -lattice diameter lines in dilations of a rational parallelogram. For \mathbf{u}\in\mathbb{Z}^{2}\setminus\{0\} , define LD_{P,u}(k) as the number of \mathbf{u} -lattice diameter lines (or segments) of kP . Proposition 3.5 . Let R be a rational parallelogram with parallel edges in direction \mathbf{u} that each contain an integral vertex. Then there exists a positive integer q such that \LD_{R,u}:\mathbb{N}_{\geq q}\to\mathbb{N} agrees with a quasi-polynomial function of degree one whose period divides q . Proof. After applying a unimodular transformation, we may assume that (0,0) is a vertex of R and that \mathbf{u}=(1,0) . Let the other two parallel edges, adjacent to those in direction \mathbf{u} , have direction (a,q) for some a,q\in\mathbb{Z},q>0 . Then, one of the edges in direction \mathbf{u} has the form [(0,0),(\frac{p}{q},0)] and without loss of generality p>0 . This edge contains a \mathbf{u} -lattice diameter segment. Furthermore, the other edge emanating from the origin has the form [(0,0),\lambda(a,q)] for some \lambda=\frac{w}{q} and again we can assume w\in\mathbb{N} . That is, \lambda(a,q)=(\frac{aw}{q},w) . Let k\in\mathbb{N} be a dilation factor. The lattice width of kR in direction (0,1) is kw . For j\in\{0,\ldots,kw\} , define the lines on height j as L_{j}=(0,j)+\spn(\{(1,0)\}) and denote the corresponding segments by S_{j}(k)=L_{j}\cap kR . When k=1 we just write S_{j} . Let \mathcal{L}(k)=\{S_{j}(k)\,\mathrm{:}\,j\in\{0,\ldots,kw\}\} , that is, all \mathbf{u} -lattice segments that intersect kR . For a segment S\subseteq\mathbb{R}^{2} , let S_{{\mathbb{Z}}}:=\conv(\{S\cap\mathbb{Z}^{2}\}) . So S_{j}(k) contains a \mathbf{u} -lattice diameter segment if and only if S_{j}(k)_{\mathbb{Z}} is a \mathbf{u} -lattice diameter segment. Claim 1: \nvol(S_{j}(k))-\nvol(S_{j}(k)_{\mathbb{Z}})<1 if and only if S_{j}(k)_{\mathbb{Z}} is a \mathbf{u} -lattice diameter segment. It suffices to show this for k=1 since R is arbitrary. All S_{j} have the same length, and S_{0} is a lattice diameter segment since it contains a vertex. By Lemma 2.1 \displaystyle|S_{0}\cap\mathbb{Z}^{2}|=\lfloor\nvol(S_{0})\rfloor+1=\lfloor\nvol(S_{j})\rfloor+1\geq|S_{j}\cap\mathbb{Z}^{2}|=\nvol({S_{j}}_{\mathbb{Z}})+1. Thus |S_{0}\cap\mathbb{Z}^{2}|=|S_{j}\cap\mathbb{Z}^{2}| if and only if \lfloor\nvol(S_{j})\rfloor+1=\nvol({S_{j}}_{\mathbb{Z}})+1 which holds if and only if \nvol(S_{j})-\nvol(S_{j{\mathbb{Z}}})<1 . This proves Claim 1 . Claim 2: \mathbf{u} -lattice diameter segments S_{j}(k)_{\mathbb{Z}} are determined by j\pmod{q} . Let \chi_{k}:\{0,\ldots,kw\}\to\{0,1\} be the indicator function with \chi_{k}(j)=1 if and only if L_{j} is a \mathbf{u} -lattice diameter line of kR . Let j,j^{\prime}\in\{0,\ldots,kw\} with j^{\prime}=j+tq for some t\in\mathbb{N} . Then S_{j^{\prime}}(k)=S_{j}(k)+(ta,tq) , and S_{j^{\prime}}(k)_{\mathbb{Z}}=S_{j}(k)_{\mathbb{Z}}+(ta,tq) . Thus \displaystyle\nvol(S_{j}(k))-\nvol(S_{j}(k)_{\mathbb{Z}})=\nvol(S_{j^{\prime}}(k))-\nvol(S_{j^{\prime}}(k)_{\mathbb{Z}}) and by Claim 1 S_{j}(k)_{\mathbb{Z}} is a \mathbf{u} -lattice diameter segment of kR if and only if S_{j^{\prime}}(k)_{\mathbb{Z}} is. Claim 3: \mathbf{u} -lattice diameter segments S_{j}(k)_{\mathbb{Z}} are determined by k\pmod{q} . Let j\in\{0,\ldots,kw\} and i\in\{0,\ldots,q-1\} . If S_{j}(k)=[\mathbf{a},\mathbf{b}] , then S_{j}(i)=[\mathbf{a},\mathbf{b}+((k-i)\frac{p}{q},0)] . When k\equiv i\pmod{q} the right endpoints of S_{j}(k) and S_{j}(i) differ by a vector in \mathbb{Z}\times\{0\} , so \displaystyle\nvol(S_{j}(k))-\nvol(S_{j}(k)_{\mathbb{Z}})=\nvol(S_{j}(i))-\nvol(S_{j}(i)_{\mathbb{Z}}). By Claim 1 it follows that S_{j}(k)_{\mathbb{Z}} is a \mathbf{u} -lattice diameter segment of kR if and only if S_{j}(i)_{\mathbb{Z}} is a \mathbf{u} -lattice diameter segment of iR . The counting function: Note that q and w are values that only depend on R . Let i\in\{0,\ldots,q-1\} , and let k=\tilde{k}q+i for some \tilde{k}\in\mathbb{N} . Define a q -block of kR as the set of lines L_{tq},\ldots,L_{tq+q-1} for those t\in\mathbb{N} for which tq+q-1\leq kw . The number of q -blocks in kR is \displaystyle\blocks_{i}(k)=\left\lfloor\frac{kw+1}{q}\right\rfloor=\tilde{k}w+\left\lfloor\frac{iw+1}{q}\right\rfloor=\frac{wk}{q}-\left(\frac{iw}{q}-\left\lfloor\frac{iw+1}{q}\right\rfloor\right), which is a linear function in k . Next we count the number of \mathbf{u} -lattice diameter lines in kR per q -block. By Claim 3 , this only depends on the congruence class k\bmod q . Take q+i as a representative for i\bmod q , since it has at least one q -block, and let \displaystyle n_{i}:=\sum_{j=0}^{q-1}\chi_{q+i}(j)=\#\{L_{j}:j=0,\ldots,q-1,\,L_{j}\text{ is a $\mathbf{u}$-lattice diameter line of }(q+i)P\}. Define \rem_{i} as the number of lattice lines intersecting kR not contained in a q -block, then \rem_{i}=iw+1\bmod q . Clearly kw+1\equiv iw+1\pmod{q} . The number of those lines that are \mathbf{u} -lattice diameter lines is \displaystyle r_{i}:=\sum_{j=0}^{\rem_{i}}\chi_{i}(j)=\#\{L_{j}:j=0,\ldots,\rem_{i},\,L_{j}\text{ is a $\mathbf{u}$-lattice diameter line of }iP\}. Together we get \LD_{R,u\,}(k)=n_{i}\cdot\blocks_{i}(k)+r_{i} which for fixed congruence class i\bmod q is a linear function in k . Thus \LD_{R,u} agrees with a quasi-polynomial function of degree one, whose period divides q . ∎ Now we are ready to prove the main theorem of this subsection. Theorem 3.6 . Let P be a lattice polygon. There exists a positive integer q such that \LD_{P}:\mathbb{N}_{\geq q}\to\mathbb{N} agrees with a quasi-polynomial function of degree one whose period divides q . Proof. Let L be a lattice diameter line of P such that \nvol(L\cap P) is maximal among all lattice diameter lines of P . Let \nvol(L\cap P)=\frac{p}{q} for p,q\in\mathbb{N} . By Lemma 3.2 there exists a set \mathcal{D} that is the set of diameter directions of kP for all k\geq q . By [ AI87 , Theorem 4.1] , |\mathcal{D}|\leq 4 . Let k\geq q . By Lemma 3.3 , \nvol(L\cap P) is the same for all lattice diameter lines L of kP . Let \mathcal{D}=\mathcal{D}_{=1}\cup\mathcal{D}_{>1} , where \mathbf{u}\in\mathcal{D}_{=1} if kP has exactly one \mathbf{u} -lattice diameter line and otherwise \mathbf{u}\in\mathcal{D}_{>1} . As in the proof of Lemma 3.4 , for \mathbf{u}\in\mathcal{D}_{>1} , there exist vertices \mathbf{v}_{i},\mathbf{v}_{i+1} of P such that all \mathbf{u} -lattice diameter lines are contained in the dilated rectangle k\cdot R(\mathbf{u}) for R(\mathbf{u}):=P\cap H^{+}(\mathbf{a},\langle\mathbf{a},\mathbf{v}_{i}\rangle)\cap H^{-}(\mathbf{a},\langle\mathbf{a},\mathbf{v}_{i+1}\rangle) , where \mathbf{a}\in\mathbf{u}^{\perp}\setminus\{0\} . Then \displaystyle\LD_{P}(k)=\sum_{\begin{subarray}{c}R=R(\mathbf{u})\\ \mathbf{u}\in\mathcal{D}_{>1}\end{subarray}}\LD_{R,\mathbf{u}\,}(k)+\sum_{\begin{subarray}{c}\mathbf{u}\in\mathcal{D}_{=1}\end{subarray}}1 and by Proposition 3.5 , \LD_{R,\mathbf{u}\,}(k) agrees with a quasi-polynomial function of degree one whose period divides q , so \LD_{P}(k) does as well. ∎ We return to Example 3.1 and demonstrate how we obtain the claimed quasi-polynomial. Example 3.7 . P=\conv(\{(0,0),(1,3),(5,1),(6,4)\}) and its dilates 2P and 3P are depicted in Figure 7 with their lattice diameter segments. P has one diameter direction \mathbf{u}=(1,0) , so \mathcal{D}=\{(1,0)\} . All lattice diameter segments of P are contained in the parallelogram R=\conv(\{(1/3,1),(1,3),(17/3,3)\}) . The slope of the left edge is 3 which implies that the period of \LD_{R,\mathbf{u}} is q=3 , and the lattice width of R in direction (0,1) is w=2 . Theorem 3.6 guarantees a quasi-polynomial behavior for values k\geq q , but here we actually get it for all k\in\mathbb{N} . Figure 7 : Lattice diameter segments in dilates of P to visualize the values n_{i},\rem_{i},r_{i} and \blocks_{i} . For i\in\{0,1,2\} and k\equiv i\pmod{3} we partition the \mathbf{u} -lattice lines that intersect kR into \blocks_{i}(k) q -blocks and \rem_{i} remaining lattice lines. Here, R and 2R have one q -block, and 3R has two q -blocks. These examples suffice to read off n_{i} , the number of lattice diameter lines per q -block, and r_{i} , the number of lattice diameter lines in the remaining \rem_{i} lines, of kR for any k . We get i n_{i} \blocks_{i}(k) \rem_{i} r_{i} 1 3 \tfrac{1}{3}(2k+1) 0 0 2 2 \tfrac{1}{3}(2k-1) 2 2 0 1 \tfrac{1}{3}(2k) 1 1. Then, as in the proof of Theorem 3.6 , \displaystyle\LD_{P}(k)=\LD_{R,(1,0)}(k)=n_{i}\cdot\blocks_{i}(k)+r_{i}=\begin{cases}2k+1&\text{if }k\equiv 1\pmod{3},\\ \frac{4}{3}k+\frac{4}{3}&\text{if }k\equiv 2\pmod{3},\\ \frac{2}{3}k+1&\text{if }k\equiv 0\pmod{3}.\end{cases} We conjecture that counting lattice diameter segments or more generally counting \ell -slices of P that contain the most lattice points among all \ell -dimensional slices of P have a similar behavior under dilation of P . More precisely: Conjecture 2 . Let P be a lattice d -polytope, and \ell\in[d] . Define \LD_{P}^{\ell}(k) as the number of \ell -dimensional slices of P that contain the most lattice points among all \ell -dimensional slices of P . Then there exists a positive integer q such that \LD_{P}^{\ell}:\mathbb{N}_{\geq q}\to\mathbb{N} agrees with a quasi-polynomial function of degree d-\ell . A proof would require new ideas. For example, in many parts of our proof we rely on the fact that for every diameter direction, lattice diameter segments exist that pass through vertices. As shown in Example 2.6 this does not hold when d\geq 3 . Furthermore, the relation between the number of lattice points on an \ell -slice and its normalized volume, as described in Lemma 2.1 , is more subtle in higher dimensions. 4 Diameter directions and the discrete Borsuk partition problem We begin with Theorem 4.3 which bounds the number of diameter directions of a lattice polytope. Thereafter, we expand our study of lattice diameters to bounded sets S\subset\mathbb{Z}^{d} . Note that if S=\conv(S)\cap\mathbb{Z}^{d} , then \ldiam(S)=\ldiam(\conv(S)) , where \conv(S) is a lattice polytope, but our results hold for any discrete set of lattice points S . In Lemma 4.6 , we prove an upper bound on the number of lattice diameter segments that end at a given point in S . Using this, we prove Theorem 4.8 , the discrete Borsuk partition problem. A lemma which will be of much use in this section, from [ Rab89 ] , is the following: Lemma 4.1 (Rabinowitz, 1989) . Let S\subseteq\mathbb{Z}^{d} be a bounded set and let m\in\mathbb{N} satisfy |S|>m^{d} . Then \conv(S) has at least m+1 collinear points. In other words, if \ldiam(S)1 ; see Figure 8 for an example. Figure 8 : Lattice diameter lines colored by their diameter direction. We show an analogous statement to the first part, when \ldiam(P)=1 , in higher dimensions. Our computational experiments suggest that an even smaller bound holds when \ldiam(P)>1 , but this remains an open problem. Define the direction \dir(\mathbf{x},\mathbf{y}) between two points \mathbf{x},\mathbf{y}\in\mathbb{R}^{d} as \mathbf{y}-\mathbf{x} or any of its non-zero multiples. For X\subseteq\mathbb{R}^{d} (usually discrete) define the set of its directions as \displaystyle\dir(X):=\left\{\dir(\mathbf{x}_{1},\mathbf{x}_{2}):\mathbf{x}_{1},\mathbf{x}_{2}\in X,\ \mathbf{x}_{1}\neq\mathbf{x}_{2}\right\}. Lemma 4.2 . Let X,Y\subseteq\mathbb{R}^{d} be sets contained in parallel hyperplanes H(\mathbf{a},\alpha) and H(\mathbf{a},\beta) , respectively. Suppose that \dir(X)\cap\dir(Y)=\emptyset . Then all \dir(\mathbf{x},\mathbf{y}) where \mathbf{x}\in X and \mathbf{y}\in Y are pairwise distinct . Proof. Suppose there exist two distinct pairs (\mathbf{x}_{1},\mathbf{y}_{1}),(\mathbf{x}_{2},\mathbf{y}_{2})\in X\times Y with \dir(\mathbf{x}_{1},\mathbf{y}_{1})=\dir(\mathbf{x}_{2},\mathbf{y}_{2}) , that is, \mathbf{x}_{1}-\mathbf{y}_{1}=\lambda(\mathbf{x}_{2}-\mathbf{y}_{2}) for some non-zero \lambda\in\mathbb{R} . Then, since \mathbf{x}_{i}\in X\subseteq H(\mathbf{a},\alpha) and \mathbf{y}_{i}\in Y\subseteq H(\mathbf{a},\beta) we have \displaystyle 0\neq\alpha-\beta=\langle a,\mathbf{x}_{1}-\mathbf{y}_{1}\rangle=\langle a,\lambda(\mathbf{x}_{2}-\mathbf{y}_{2})\rangle=\lambda\langle\mathbf{a},\mathbf{x}_{2}-\mathbf{y}_{2}\rangle=\lambda(\alpha-\beta) and thus \lambda=1 . It follows that \mathbf{x}_{1}-\mathbf{x}_{2}=\mathbf{y}_{1}-\mathbf{y}_{2}\in\dir(X)\cap\dir(Y) , a contradiction. ∎ Theorem 4.3 . Let P be a lattice d -polytope, with \ldiam(P)=1 . Then P has at most \binom{2^{d}}{2} diameter directions and this bound is best possible. Proof. Let d\in\mathbb{N} . For d=1 the claim is clear, so assume d\geq 2 . Since \ldiam(P)<2 , by 4.1 |P\cap\mathbb{Z}^{d}|\leq 2^{d} . A lattice diameter line is determined by two lattice points in P , so the number of possible diameter directions is bounded above by \binom{2^{d}}{2} . Next, we give a construction of a lattice d -polytope attaining this bound. For t\in\mathbb{N} and x\in\mathbb{N}_{\geq 3} , let \displaystyle\mathbf{v}_{1}=(1,t),\ \mathbf{v}_{2}=(x,tx+1),\ \mathbf{v}_{3}=(-x-1,-tx-t-1) and let T_{t,x}=\conv(\{\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3}\}) . Then (0,0)=\frac{1}{3}\mathbf{v}_{1}+\frac{1}{3}\mathbf{v}_{2}+\frac{1}{3}\mathbf{v}_{3}\in T_{t,x} and since T_{t,x} has area \frac{3}{2} , Pick’s Theorem [ Pic99 ] implies that T_{t,x} contains no lattice points besides (0,0) . Moreover, no three points in T_{t,x} are collinear, thus \ldiam(T_{t,x})=1 . The slopes of the six diameter lines in T_{t,x} are \displaystyle t,\ t+\dfrac{1}{2x+1},\ t+\dfrac{1}{x+2},\ t+\dfrac{1}{x+1},\ t+\dfrac{1}{x},\text{ and }\ t+\dfrac{1}{x-1}, which are all distinct and contained in [t,t+\frac{1}{2}] . Induction Claim: For k\in\{2,\ldots,d\} there exist 2^{d-k} lattice k -polytopes P_{1},\ldots,P_{2^{d-k}} such that |P_{i}\cap\mathbb{Z}^{k}|=2^{k} , P_{i} has \binom{2^{k}}{2} diameter directions, and \dir(P_{i})\cap\dir(P_{j})=\emptyset for all i,j\in[2^{d-k}],\ i\neq j . Base Case: For k=2 consider \{T_{i,3}\,\mathrm{:}\,i=1,\ldots,2^{d-2}\} . As we showed above T_{i,3} contains 4=2^{2} lattice points, \ldiam(T_{i,3})=2 and all lines through two different lattice points have a different diameter direction, thus T_{i,3} has \binom{4}{2}=6 diameter directions. Furthermore \dir(T_{i,3})\subseteq[i,i+1/2] , thus the diameter directions of all T_{i,3} for i=1,\ldots,2^{d-2} are distinct. Induction Hypothesis: For k\in\{2,\ldots,d-1\} let P_{1},\ldots,P_{2^{d-k}} be lattice k -polytopes such that |P_{i}\cap\mathbb{Z}^{k}|=2^{k} , P_{i} has \binom{2^{k}}{2} diameter directions, and \dir(P_{i})\cap\dir(P_{j})=\emptyset for all i,j\in[2^{d-k}],\ i\neq j . In particular, any two pairs of lattice points in P_{i} define lattice diameter lines with distinct slopes. Induction Step: Let P_{i} for i\in[2^{d-k}] be as given in the induction hypothesis. Let \underline{P_{i}}:=P_{2i-1}\times\{0\} and \overline{P_{2i}}:=P_{2i}\times\{1\} and construct polytopes \displaystyle Q_{i}:=\conv\left(\left\{\underline{P_{i}},\overline{P_{2i}}\right\}\right)\subseteq\mathbb{R}^{k+1}. Since \underline{P_{i}} and \overline{P_{2i}} are contained in parallel hyperplanes \displaystyle|Q_{i}\cap\mathbb{Z}^{k+1}|=|\underline{P_{i}}\cap\mathbb{Z}^{k+1}|+|\overline{P_{2i}}\cap\mathbb{Z}^{k+1}|=2^{k+1}, and \ldiam(Q_{i})=2 . By Lemma 4.2 all \dir(\mathbf{x},\mathbf{y}) for any \mathbf{x}\in\underline{P_{i}} and \mathbf{y}\in\overline{P_{2i}} are distinct so any two points in Q_{i} define different lattice diameter lines with distinct diameter directions, i.e., Q_{i} has \binom{2^{k+1}}{2} diameter directions. Furthermore, again by Lemma 4.2 , any two diameter directions in Q_{i} and Q_{j} are distinct. This proves the induction claim. ∎ Example 4.4 . We give an example of our recursive construction using the same idea as in the proof of Theorem 4.3 . Here T_{0}=\conv(\{(0,-3),(1,-4),(5,-5)\}) and T_{1}=\conv(\{(3,-3),(4,-2),(2,-7)\}) each have 6=\binom{2^{2}}{2} distinct diameter directions and thus P=\conv(T_{0}\times\{0\},T_{1}\times\{1\}) has \binom{2^{3}}{2} diameter directions. See Figure 9 . Figure 9 : The convex hull of two lattice triangles with each \binom{2^{2}}{2} diameter directions which yields a 3 -dimensional lattice polytope with \binom{2^{3}}{2} distinct diameter directions. 4.2 The discrete Borsuk partition problem In this section we prove the discrete version of Borsuk’s partition problem for lattice diameters. More generally, we study lattice diameters of bounded sets S\subset\mathbb{Z}^{d} . Notice that the function f:\mathbb{Z}^{d}\times\mathbb{Z}^{d}\to\mathbb{R} defined by f(\mathbf{x},\mathbf{y})=\nvol([\mathbf{x},\mathbf{y}])=|[\mathbf{x},\mathbf{y}]\cap\mathbb{Z}^{d}|-1 is a semi-metric, i.e., it is positive-definite and symmetric, so (\mathbb{Z}^{d},f) is a semi-metric space. Furthermore, f satisfies f(\lambda\mathbf{x},\lambda\mathbf{y})=|\lambda|\cdot f(\mathbf{x},\mathbf{y}) for all \mathbf{x},\mathbf{y}\in\mathbb{Z}^{d} and all \lambda\in\mathbb{Z} . From this viewpoint, Theorem 4.8 is closely related to the well-known Boltyansky-Gohberg conjecture [ BG85 ] which states that any bounded set S in a d -dimensional normed space can be partitioned into at most 2^{d} subsets, each having strictly smaller diameter. Recall that for a bounded set S the lattice Borsuk number of S , denoted \beta_{\mathbb{Z}}(S) , is the smallest number of subsets into which S can be partitioned, such that each subset has strictly smaller lattice diameter than \diam_{\mathbb{Z}}(S) . In Figure 10 we show a Borsuk partition of a set S=P\cap\mathbb{Z}^{d} , where P is a lattice polygon, into parts S_{1} and S_{2} . Necessarily \ldiam(S_{i})<\ldiam(P) for i=1,2 , but note that \ldiam(\conv(S_{1}))=\ldiam(P) . P S_{2} S_{1} Figure 10 : A Borsuk partition P\cap\mathbb{Z}^{d}=S_{1}\sqcup S_{2} where \ldiam(S_{1})<\ldiam(\conv(S_{1}))=\ldiam(P) . Define the lattice Borsuk graph of S , denoted \BG_{\mathbb{Z}}(S) , as the graph with vertex set S and edges \{\mathbf{x},\mathbf{y}\}\subseteq S if and only if f(\mathbf{x},\mathbf{y})=\diam_{\mathbb{Z}}(S) . Remark 4.5 . For a bounded set S\subset\mathbb{Z}^{d} , \beta_{\mathbb{Z}}(S)=\chi(\BG_{\mathbb{Z}}(S)) , where \chi is the chromatic number of \BG_{\mathbb{Z}}(S) , i.e., the minimum number of colors needed to color S so that no two adjacent vertices in S have the same color. To find a good bound on the lattice Borsuk number it will be useful to bound \Delta(\BG_{\mathbb{Z}}(S)) , the maximum degree of the lattice Borsuk graph. This is precisely what the next lemma does. Lemma 4.6 . Let S\subset\mathbb{Z}^{d} be a bounded set and let \mathbf{x}\in S . Then, the number of lattice diameter segments in S that have \mathbf{x} as an endpoint is at most 2^{d}-1 . Therefore, \Delta(\BG_{\mathbb{Z}}(S))\leq 2^{d}-1 . Proof. If |S|<2 , then there is nothing to show, so suppose |S|\geq 2 . After an appropriate translation, we may assume that \mathbf{x}=\mathbf{0} . Define S_{\mathbf{0}}:=\{\mathbf{s}\in S:f(\mathbf{0},\mathbf{s})=\operatorname{diam}_{\mathbb{Z}}(S)\} and consider the corresponding set of vectors S^{\prime}_{\mathbf{0}}:=\left\{\frac{\mathbf{s}}{\operatorname{diam}_{\mathbb{Z}}(S)}:\mathbf{s}\in S_{\mathbf{0}}\right\}\cup\{\mathbf{0}\}. Suppose, for contradiction, that |S_{\mathbf{0}}|>2^{d}-1 , then |S^{\prime}_{\mathbf{0}}|>2^{d} , and by 4.1 , we have \operatorname{diam}_{\mathbb{Z}}(S^{\prime}_{\mathbf{0}})\geq 2 . Let \mathbf{y}^{\prime},\mathbf{z}^{\prime}\in S^{\prime}_{\mathbf{0}} such that f(\mathbf{y}^{\prime},\mathbf{z}^{\prime})\geq 2 . Since all non-zero vectors in S^{\prime}_{\mathbf{0}} are primitive, neither \mathbf{y}^{\prime} nor \mathbf{z}^{\prime} is \mathbf{0} . So for \mathbf{y}=\ldiam(S)\cdot\mathbf{y}^{\prime} and \mathbf{z}=\ldiam(S)\cdot\mathbf{z}^{\prime} we get f(\mathbf{y},\mathbf{z})=\ldiam(S)\cdot f(\mathbf{y}^{\prime},\mathbf{z}^{\prime})\geq\ldiam(S)\cdot 2, which is a contradiction. Thus |S_{\mathbf{0}}|\leq 2^{d}-1 , and \Delta(\BG_{\mathbb{Z}}(S))\leq 2^{d}-1 follows from Remark 4.5 . ∎ Now we state Brooks’ Theorem, a graph theoretic result, which relates the maximum degree of a graph to its chromatic number. For the lattice Borsuk graph this translates to a bound on \beta_{\mathbb{Z}}(S) . Brooks’ Theorem has many published proofs, see for example [ BM08 , Theorem 8.4] . Theorem 4.7 (Brooks, 1941) . If G is a connected simple graph, then \chi(G)\leq\Delta(G)+1 , with equality if and only if G is an odd cycle or a complete graph. Finally, we present a solution to the discrete version of Borsuk’s partition problem. Theorem 4.8 . Let S\subset\mathbb{Z}^{d} be a bounded set. Then \beta_{\mathbb{Z}}(S)\leq 2^{d} and this bound is best possible. Proof. By Remark 4.5 , Lemma 4.6 and Brooks’ Theorem applied to each component of \BG_{\mathbb{Z}}(S) we get \beta_{\mathbb{Z}}(S)=\chi(\BG_{\mathbb{Z}}(S))\leq\Delta(\BG_{\mathbb{Z}}(S))+1\leq 2^{d}. The set S=\{0,1\}^{d} is an example where this bound is attained. ∎ Notice that \beta_{\mathbb{Z}}(S)=2^{d} if and only if there exists an \mathbf{x}\in S that is the endpoint of 2^{d}-1 lattice diameter segments, and \BG_{\mathbb{Z}}(S) is isomorphic to the complete graph on 2^{d} vertices. Thus we conjecture the following: Conjecture 3 . Let S\subset\mathbb{Z}^{d} be a bounded set. Then \beta_{\mathbb{Z}}(S)=2^{d} if and only if \conv(S) is unimodularly equivalent to a d -cube [0,m]^{d} for any m\in\mathbb{N} . In dimension two this conjecture is true and can be proven using a characterization of lattice polygons which have four diameter directions, see [ BF01 , Theorem 2(iii)] .