As a web developer or IT admin, successfully managing multiple client accounts can be challenging. In this webinar we will look at the tools provided by Media Temple and Plesk to make managing your clients’ hosting easier.

Hi Math Experts,

Here's my question

How do you calculate the concave boundary of a set of x,y coordinates that passes through the maximum number of points?

I was able to find lots of documentation online for finding the CONVEX boundary for a set of points, but I can't seem to find

anything on CONCAVE boundaries.

-CPOsosky

Here's my question

How do you calculate the concave boundary of a set of x,y coordinates that passes through the maximum number of points?

I was able to find lots of documentation online for finding the CONVEX boundary for a set of points, but I can't seem to find

anything on CONCAVE boundaries.

-CPOsosky

Yes. It's really just a TSP, as I just indicated in my other comment. Sometimes it's very frustrating to have other comments pop up while writing your own. I don't see a solution to that problem, however.

But a concave boundary or hull doesn't need to pass through all points. Just all points need to be within. And thats the problem for it: When to choose a point to be part of the boundary or just contained.

http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html

@SteH

The original question is looking for a boundary that passes through the maximum number of points. Well, a shortest-length Hamiltonian circuit will necessarily be a polygon that passes through ALL the points (can't do better than that) and whose edges don't intersect. Traveling salesman problems are all about finding such cycles. Although finding a solution to a TSP is hard, finding Hamiltonian circuits whose edges don't intersect is quite straightforward. Such techniques abound in the literature of traveling salesman problems.

The problem is the arbitrary shape of the concave polygon that leads to multiple solutions.

The left side of the green figure could have just as easily been drawn using several of the internal points,

creating several "dents" on the left side.

-CPOsosky

All Courses

From novice to tech pro — start learning today.

A first idea is to use a point inside if it is nearer to one of the boundary than the next on the boundary. Try expermenting.