Advanced search

For the mathematicians amongst you ...

(22 Posts)
blinkinheck Tue 25-Nov-14 23:49:00

If you have a cluster of n randomly distributed geographical points within a polygon, and you want to calculate the location of a new point that is also within the polygon but which is as far as possible from all of the other points, is there a standard way of doing it?

blinkinheck Wed 26-Nov-14 06:54:25

I don't think its weighted mean centres because that will pull the new point closer to the cluster. I perhaps need something that is the inverse of that.

TeenAndTween Wed 26-Nov-14 10:01:14

Oooh. That sounds interesting. No idea, not sure I even ever did.

bobs123 Wed 26-Nov-14 10:04:09

Marking place to ask DD when she comes home from school (Doing A Level Maths)
Me? haven't the foggiest grin

lljkk Wed 26-Nov-14 10:13:11

THIESsen polygons, but I'd have to puzzle the algorithm out unless it already exists.
Geography not math problem.

TeenAndTween Wed 26-Nov-14 11:40:46

Suppose all the points already are at (x1,y1) (x2, y2) etc.

Your point is going to be at (a,b)

The distance your point is away from any point (X, Y)

is sqrt( (X-a)^2 + (Y-b)^2) ) (Pythag).

So you need the value of (a,b) for which the sum of all the Distances is greatest, but for which (a,b) is within your polygon.

You could solve it using a sledgehammer via a computer program under those conditions I guess.

As a matter of interest, why do you want to know?

Can't work out whether you could turn it into 2 linear problems, solving for a and b separately. That would probably make it 'trivial'.

skylark2 Wed 26-Nov-14 11:54:23

I don't think you can solve a and b separately because for a you'll just get plus and minus infinity.

I'm also not sure that you want the sum of the distances - don't you want to maximise the minimum distance?

I'm also thinking brute force and computation, but that may be coloured by me being a computer programmer these days and not having done any pure maths in a while...

bobs, don't terrify your daughter if she can't do it. I think it's quite hard.

TeenAndTween Wed 26-Nov-14 12:02:13


You won't get plus or minus infinity as they have to be within the polygon. If all the points are on the edge of the polygon, you'd expect the required point to end up dead centre. (Though my gut feel is that you can't separate the problem).

Sum the distances or maximise the minimum distance depends on what 'as far away as possible from all of the other points' means.
Does it mean 'so that the distance to the nearest point is as large as possible' or does it mean 'so that the average distance to the other points is as large as possible' ? OP Which do you mean?

(I preferred computational maths to pure maths)

PausingFlatly Wed 26-Nov-14 12:04:50

Definitely can't solve for a and b separately, as answers are dependent. Also bloody hard to do by algorithm unless your polygon is "nice".

Erm, that wasn't very helpful, was it?

I think I'd try to generate the locus of points 1 away from all current points, 2 away from current points, 3 away... Like contour lines.

And then overlay on your polygon and see what's still inside.

Agree that geographers or maybe logistics managers may have a standard solution!

PausingFlatly Wed 26-Nov-14 12:05:33

Oh, assuming the meaning was "distance to nearest point is as large as possible".

TeenAndTween Wed 26-Nov-14 12:08:22

So Pausing you are going for 'distance to the nearest point is as large as possible' rather than my interpretation?

OP - are you trying to work out where in the UK you can live away from any possible in-laws?? grin

TeenAndTween Wed 26-Nov-14 12:08:45


PausingFlatly Wed 26-Nov-14 12:09:55

grin at in-law avoidance!

PausingFlatly Wed 26-Nov-14 12:14:14

(Oops, that sounded like I was calling other posters unhelpful: no, just myself.)

howtodrainyourflagon Wed 26-Nov-14 22:29:29

Construct the Voronoi regions around the points then check the vertices of those regions one by one.

blinkinheck Wed 26-Nov-14 23:23:00

Thanks all. My DH worked out how to do it iteratively using Excel Solver.

We were actually trying to find the point in the Local Authority that was furthest away from any of the local schools (don't ask!), but I like the in-law idea too. smile

bobs123 Wed 26-Nov-14 23:26:58

I liked the in-law idea too grin
I asked DD (doing Geography A Level as well as Maths) - she looked at me blankly!!!!! confused
Glad you got it sorted!

NoSundayWorkingPlease Sun 30-Nov-14 00:19:20

I got an A at A Level maths, 9 years ago.

I have no friggin idea what that op means. Having children has literally killed my brain I think :/

blinkinheck Sun 30-Nov-14 08:31:38

Don't worry NoSunday. DH is an Operational Research professional, so optimisation techniques are his bread and butter - I should have thought to ask him in the first place!

PausingFlatly Sun 30-Nov-14 10:57:13

grin at high regard for MN that you asked here before asking your very own Op Research expert!

blinkinheck Sun 30-Nov-14 11:15:08

He was at work! grin

blinkinheck Sun 30-Nov-14 11:16:05

Actually no, looking at the time of my OP .... he'd gone to bed! blush

Join the discussion

Join the discussion

Registering is free, easy, and means you can join in the discussion, get discounts, win prizes and lots more.

Register now