TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Monday, March 29, 2021

On 'Deployment' and 'Dispersal'

A basic intro to these classes of problems is given in Stanley Ogilvy's 'Tomorrow's Math'

Deployment: To place a specified number n of station points in a region such that the maximum distance of any point in the region from one of the stations is minimized.

Dispersal: To place n station poits in a region such that the minimum distance among the stations is maximized.

Example: It is not possible to scatter (disperse) 5 points on a sphere so that every pair of them is separated by more than 90 degrees. The same statement is true for 6 points. For dispersal 5 points and 6 points give same result.

Question: What is the status of dispersal on a triangular region?

Remark 1: For n =2, it is best to place the stations at the ends of the longest side. For any higher n, it appears that 2 of the stations should be kept at the ends of the longest side. For n =3, the third station is either (a) the third vertex of the triangle or (b) the point where the perpendicular bisector of the longest side cuts the rest of the triangle. Beyond that, things are less clear.

Remark 2: Reg best deployment of n points on a triangular region, even for n = 2, things are far from obvious. Wonder if there are any special properties to the Voronoi regions that can result when n stations are optimally deployed - whether the regions will have say equal area.

Discussion page on this: https://mathoverflow.net/questions/388977/deployment-and-dispersion-in-triangular-regions

0 Comments:

Post a Comment

<< Home