Is "Concave Hull" correct terminology?

Question

Can we call the envelop of a set of points having non-convex boundary as "Concave Hull"?

Answer 1

You sort of can, but the definition of the boundary becomes strange. For example, you can always find a non-intersecting polygon that has all the points in the set as vertices, and consider this your "concave hull."

As a proof, join the dots in a cycle in any order and number them with this order (so for $n$ points we will have points $P_i$ for $1\leq i \leq n$ with $P_i$ immediately before $P_{i+1}$ where subscripts are taken modulo n).

Now suppose that two edges $P_a P_{a+1}$ and $P_b P_{b+1}$ cross. These are diagonals of a convex quadrilateral $P_a P_b P_{a+1} P_{b+1}$, and so we have $|P_a P_b| + |P_{a+1}P_{b+1}| < |P_aP_{a+1}| + |P_b P_{b+1}|$. So the total sum of lengths decreases. Note that there are a finite number of orderings of the $n$ points, so we choose one with minimal sum of lengths. Then no two edges can cross, since we could use the operation to decrease the sum of lengths, causing a contradiction. So this polygon has no crossings.