1
$\begingroup$

Given 4 vertices:

(-3.2, 0.8), (-3.2, -0.8), (3.2, -0.8), (3.2, 0.8)

A function which I did not write, and given vertices, will return the points of a convex hull.

Using the points above, it returns these points:

(-3.2, 0.8), (-3.2, -0.8), (3.2, -0.8), (3.2, 0.8), (-3.2, 0.8)

Is it improper to have a duplicate point?

Sometime tells me it is, but I'd hate to suggest to the author that he made a mistake when he did not.

$\endgroup$
  • 3
    $\begingroup$ Maybe the program is outputting one complete circuit around the corner points of the hull, and so last value equals first. You'd need to post the algorithm here to get an answer on this. $\endgroup$ – coffeemath Aug 24 '13 at 0:12
  • $\begingroup$ Why would anyone need to see the algorithm? My question is whether a hull can have an extra point or not and still be considered a hull. $\endgroup$ – Joncom Aug 24 '13 at 2:52
2
$\begingroup$

The convex hull (call this $H$) of points $P_1,\cdots P_n$ is the set of combinations $$\sum_{k=1}^n c_kP_k$$ where each $c_k \ge 0$ and the sum of the $c_k$ is 1. If a copy of one of the points, say $P_n$ is adjoined to the list $P_1,\cdots P_n$, the now possibly different hull, call it $H'$ is by the above definition the set of combinations $$c_{n+1}P_n+\sum_{k=1}^n c_kP_k$$ where now all the $c_k,\ k=1,2,...,n+1$ are nonnegative and their sum is $1$. Now the claim is that in fact $H'=H$ as sets, i.e. the hulls are the same. It's clear that $H \subset H'$ by taking $c_{n+1}=0$. For the reverse direction, define a new coefficient name $e_n=c_n+c_{n+1}$ and note that now $H'$ is given by the set of combinations $$\sum_{k=1}^{n-1} c_kP_k+e_nP_n.$$ The constraints on these $n$ coefficients are again that they be each nonnegative and sum to $1$. This then shows that $H' \subset H$, and we arrive at the claimed statement, that adding a copy of a point in describing a convex hull has no effect on the hull generated.

$\endgroup$

Your Answer

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

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