# Which algorithm to find the shortest (nodes count) path that encompasses all polygons inside a larger polygon?

Inside a large polygon (say the USA boundaries) I need to find the shortest path that will encompass smaller polygons
(say the following cities: Kansas city, St Louis, Memphis, Oklahoma City)

By shortest I mean with the less nodes as possible. (then will the smaller inner surface)

A 'not-that-bad' result will be the bounding rectangle that comprises the 4 cities
A better one will be a triangle (3 nodes < 4) New York, San Antonio, Seattle
An even better would be the triangle Minneapolis, Louisville, El Paso because surface is less than previous one

Exemple For non US

imagine a large rectangle 0,0 => 1000,1000
inside 4 points 490,490 ; 490,510 ; 510,510 ; 510,490
a good result : rectangle 490,490 => 510,510
a better result : large triangle 490,0 490,490 1000,490
an even better : small triangle 490,490 ; 530,490 490,530

Is there a well known algorithm for this ?

• Sounds like homework. Show us what you've tried or tried to learn or google and not found. Jul 2, 2015 at 22:16
• Are you looking for line simplification? Jul 2, 2015 at 23:27
• This is not homework. (Or yes this is DIY home work). What I've tried ? Paper and pen. I would start to compute the convex hull. Then for each segment I would create a rect bounding box that goes through this segment. If the bounding box fits inside the main polygon then I got a 4nodes path. If not, then I will : intersect bounding box with surrounding polygon, simplify the spikes of surrounding polygon that goes into my bounding box. Then I'll keep the path with the less node. Jul 3, 2015 at 8:29