# Finding the linear functions defining a polyhedron through integer data?

Let's say I have a bunch of linear functions $$f_1,\cdots,f_n$$ in $$k$$ variables; then $$f_1,\cdots, f_n\le0$$ defines a polyhedron $$P$$ in the $$k$$-dimensional space.

What I'm looking for is going the other way: given data points inside a polyhedron $$P$$, is there an efficient/fast way to find the functions $$f_1,\cdots,f_n$$ cutting the polyhedron? Those data points are finitely many integer points (i.e. points whose all coordinates are integers) and $$P$$ is "the smallest" polyhedron containing them. Basically I require two things:

1. $$P$$ does not contain any other integer points.

2. The linear functions themselves have integer coefficients.

A naive way would be to loop over all possible candidate functions (their integer coefficients) in a certain range but there should be a much better/faster/efficient way of doing it.

I am not specifically looking for an answer to this problem, rather a reference or direction for where I should be looking at. Has this been studied at all? I understand that this is not exactly what linear/integer programming is about, so apologies if the question is not appropriate for this site.

• It might be pretty hard to ensure that $\mathbf{P}$ contains no other integer points. Consider for example the data points $\{(1,1),(3,1),(1,3),(3,3)\}$ with the description $\mathbf{P}=\{x\in\mathbb{R}^2:1\leq x_1\leq 3, 1\leq x_2\leq 3\}$. Here the point $(2,2,)$ is contained in $\mathbf{P}$ but not in the list of data points.
– Sune
Oct 2 '19 at 8:33
• @Sune My data points are generated through a process that can guarantee I have them all. I am effectively trying to find patterns in that process, that for reasons I won't get to now, I am almost certain will be linear in nature. Oct 2 '19 at 14:55