The integer-lattice tag has no wiki summary.
14
votes
1answer
565 views
Solving a linear diophantine equation approximately
Consider the following problem:
Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
1
vote
1answer
121 views
Most optimal parallel method for calculating the integral of a 2D function
I posted already this question to SO but got no answer so I try it now here:
In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance ...
1
vote
0answers
146 views
The Number of Short Vectors in a Lattice [closed]
Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the ...
24
votes
1answer
652 views
Random self-avoiding lattice cycle within a given bounding box
In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all ...
11
votes
2answers
419 views
What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?
I asked this question some weeks ago at mathoverflow, but I got no reply.
Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid ...
7
votes
3answers
618 views
Tree decomposition for planar graphs
First asked on math.SE with no replies.
Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition?
What is the optimal tree decomposition of a $d$-by-$d$ square grid? ...
10
votes
2answers
400 views
Complexity of hidden polygon puzzle on square grids?
Hiroimono
is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle.
The problem is:
Input: Given a set of points on on a $n$x$n$ square grid and ...
