4
$\begingroup$

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.

enter image description here

$\endgroup$

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
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ The figure doesn't look 3d $\endgroup$ – jkabrg Sep 22 at 11:45
  • $\begingroup$ Also, there's a Computer Science SE and a Theoretical Computer Science SE. I'm wondering if this question would be more appropriate there... $\endgroup$ – jkabrg Sep 22 at 11:46
  • $\begingroup$ This fugure's points are plotted on the plane v1 + v2 + v3 = 7. So, it's a pseudo 3D. $\endgroup$ – Smith Sep 22 at 11:53
  • $\begingroup$ Could you show me the URL for Computer Science forum? $\endgroup$ – Smith Sep 22 at 11:54
  • 2
    $\begingroup$ This is for all questions: cs.stackexchange.com. This is for only research level questions: cstheory.stackexchange.com/users/34621/jkabrg $\endgroup$ – jkabrg Sep 22 at 12:04
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer. It seems only for 3D, right? $\endgroup$ – Smith Sep 22 at 12:39
  • 1
    $\begingroup$ @Smith: No, the notion has been explored in 2D, 3D, and higher dimensions. I added a citation specifically for 2D. $\endgroup$ – Joseph O'Rourke Sep 22 at 12:46
  • $\begingroup$ I see, thanks a lot. $\endgroup$ – Smith Sep 22 at 12:51
  • $\begingroup$ @Smith: And similar notions hold for the triangular lattice in your example. $\endgroup$ – Joseph O'Rourke Sep 22 at 18:17
5
$\begingroup$

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:

enter image description here

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.