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. This fugure's points are plotted on the plane $v_1 + v_2 + v_3 = 7$. So, it's a pseudo 3D, e.g., green ones are $(2, 4, 1)$ and $(3, 1, 3)$.

enter image description here

  • 1
    $\begingroup$ Neither of those green points looks to me like it is inside the convex hull -- neither is a convex combination of the blue points. What is your definition of "convex" here? $\endgroup$ – j_random_hacker Sep 23 '19 at 19:39
  • $\begingroup$ You are right that blue points are not convex here. We want to look for the green points to fill the hollow, which is the definition of the convex I though. $\endgroup$ – Smith Sep 25 '19 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.