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

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ The figure doesn't look 3d $\endgroup$
    – wlad
    Commented Sep 22, 2019 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$
    – wlad
    Commented Sep 22, 2019 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
    Commented Sep 22, 2019 at 11:53
  • $\begingroup$ Could you show me the URL for Computer Science forum? $\endgroup$
    – Smith
    Commented Sep 22, 2019 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$
    – wlad
    Commented Sep 22, 2019 at 12:04

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. It seems only for 3D, right? $\endgroup$
    – Smith
    Commented Sep 22, 2019 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
    Commented Sep 22, 2019 at 12:46
  • $\begingroup$ I see, thanks a lot. $\endgroup$
    – Smith
    Commented Sep 22, 2019 at 12:51
  • $\begingroup$ @Smith: And similar notions hold for the triangular lattice in your example. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 22, 2019 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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .