I know some algorithms which compute the convex hull in a continuous space. Are there efficient algorithms to compute it in a discrete domain? For example in 3D discrete space, given the blue points, we want the convex hull including the green points.
closed as off-topic by RP_, Chris Godsil, user44191, Leo Alonso, Per Alexandersson Sep 23 at 11:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question does not appear to be about research level mathematics within the scope defined in the help center." – RP_, Chris Godsil, Per Alexandersson
There is a notion called the "orthogonal convex hull," or the "digital convex hull," which may be what you seek. For example, in this paper,
Karmakar, Nilanjana, and Arindam Biswas. "Construction of 3D Orthogonal Convex Hull of a Digital Object." In International Workshop on Combinatorial Image Analysis, pp. 125-142. Springer, Cham, 2015. Springer link.
the authors define it this way: "Orthogonal convex hull of a digital object in 3D domain is defined as the minimum volume orthogonal polyhedron enclosing the object such that its intersection with an axis-parallel face plane is either empty or a collection of projection-disjoint convex polygons."
Here's another image, specifically in 2D:
Image from P. Bhowmick's slides (PDF).
A. Biswas, P. Bhowmick, M. Sarkar, B. B. Bhattacharya, "A linear-time combinatorial algorithm to find the orthogonal hull of an object on the digital plane," Information Sciences, 216, pp. 176–195, 2012. Elsevier link.
Maybe the most general notion that would be relevant here is geodesic convexity, which can be defined in any graph. (See, for example, the book Geodesic Convexity in Graphs by Ignasio M. Pelayo.)
Here, given any graph $G$, a set of vertices $S \subseteq V(G)$ is convex if, for any vertices $u,v \in S$, every shortest $u,v$-path stays in $S$. As usual, the convex hull of a set is the smallest convex set containing it, or equivalently the intersection of all convex sets containing it. So, in your example, a convex set containing all the blue points would also have to contain the green ones, due to the geodesics below:
As suggested by the book I cited above, we can compute the convex hull in a graph by repeated use of breadth-first search. Pick a starting vertex $s \in S$, and do a breadth-first search from $s$ until you reach every vertex of $S$; every vertex on a shortest path to those must be added to $S$. Repeat this, not just for every vertex in $S$, but also for every vertex found along the way.