Sunday, March 16, 2014

[whdqmdzh] Path through plots

A region is divided into disjoint plots.  Each plot is has a price.  Given two points in the region, find the path which minimizes the total price of plots the path goes through.  This approximates buying property (eminent domain) to put in a rail line or road.

Let the region also be blanketed a varying function of price per unit length, which approximates the difficulty of building on the type of terrain at each point.

Let the path be a constant width not zero (so changing the above function from price per unit length to per unit area).

Find not just a minimum path between two points, but of many points: a Steiner tree.

No comments :