CGAL users discussion list

[Bernd Gaertner <>]

Hanjun Kim wrote:
> Hi all,
>
> Given a set of points in R^n, cgal finds a convex hull of it, i.e. vertices of
> the the hull.
>
> But can cgal do some sort of the converse?, i.e. given vertices( may assume
> lattice points) of  of a convex hull, can it find all lattice points in the
> hull? I looked it up, but it doesn't seem so.

No, CGAL cannot do this directly. What you want is called the integer 
hull of a set of points, and there are general techniques from discrete 
geometry and combinatorial optimization that address this. In a 
nutshell, the complexity of the known algorithms grows exponentially 
with the dimension n. Knowing this, the following brute-force approach 
can almost be considered as efficient: go through all the lattice points 
in the bounding box of the input, and for each one check whether it is 
contained in the convex hull. The latter can in fact be done without 
computing the convex hull, by linear proramming (see 
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/QP_solver/Chapter_main.html#sec:QP-iterators 
on how to do this with CGAL).

Best,
Bernd.