CODEWITHSUNDEEP
c++algorithmcomputational-geometry
Alexander
Alexander

Reputation: 29

The search for a set of points with a minimum sum of lengths to rectangles. What is the algorithm?

Good day.

I have the task of finding the set of points in 2D space for which the sum of the distances to the rectangles is minimal. For example, for two rectangles, the result will be the next area (picture). Any point in this area has the minimum sum of lengths to A and B rectangles. Which algorithm is suitable for finding a region, all points of which have the minimum sum of lengths? The number of rectangles can be different, they are randomly located. They can even overlap each other. The sides of the rectangles are parallel to the coordinate axes and cannot be rotated. The region must be either a rectangle or a line or a point.

Upvotes: 0

Views: 405

Answers (2)

Ante
Ante

Reputation: 5448

Add on Yves's answer.

As Yves described, each rectangle 'divide' plane into 9 parts and adds different distance method in to the sum. Middle part (rectangle) add distance 0, side parts add coordinate distance to that side, corner parts add point distance to that corner. With that approach plan has to be divided into 9^n parts, and distance sum is calculated by adding appropriate rectangle distance functions. That is feasible if number of rectangles is not too large.

Probably it is not needed to calculate all parts since it is easy to calculate some bound on part min value and check is it needed to calculate part at all.

I am not sure, but it seems to me that global distance map is convex function. If that is the case than it can be solved iteratively by similar idea as in linear programming.

Upvotes: 1

user1196549
user1196549

Reputation:

Hint:

The distance map of a rectangle (function that maps any point (x,y) to the closest distance to the rectangle) is made of four slanted planes (slope 45°), four quarter of cones and the rectangle itself, which is at ground level, forming a continuous surface.

To obtain the global distance map, it "suffices" to sum the distance maps of the individual rectangles. A pretty complex surface will result. Depending on the geometries, the minimum might be achieved on a single vertex, a whole edge or a whole face.

The construction of the global map seems more difficult than that of a line arrangement, due to the conic patches. A very difficult problem in the general case, though the axis-aligned constraint might ease it.

Upvotes: 1

Related Questions