## Finding points on a perimeter

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

### Finding points on a perimeter

Given a cloud of co-ordinate points that contains more than 3 different positions, what is the most efficient method to work out which points form the perimeter?

For example - using the astronomical constellation of orion, all the stars except for the central one in the belt form the perimeter of an hourglass shape. How would you easily determine this for any other number/arrangement of stars?

Is it possible to work this out without using Pythagoras or Trigonometry?

Is it possible to work it out without comparing every single point to all of the others?

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

### Re: Finding points on a perimeter

I don't know any details offhand, but this sounds related to what's called the "convex hull" of a set of points.

Perhaps the following may serve as a starting point.

http://en.wikipedia.org/wiki/Convex_hul ... _point_set

MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

### Re: Finding points on a perimeter

Thanks - that is pretty much what I was looking for - although in this case, for my example with Orion, all the stars in the belt would be inside the perimeter of the other 4 stars. I realise this is the correct answer to the question I should have asked - Thanks

Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

### Re: Finding points on a perimeter

You may also want to read up on Graham scan, which is a speedy algorithm to calculate the convex hull which I have used before with much success.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

### Re: Finding points on a perimeter

Regarding Convex hulls:

The convex hull is just that: convex. As such, you won't be able to achieve the hourglass shape you're looking for, since that's non-convex. To get the exterior points of a non-convex hull, there are other tricks you can play, such as "lifting" the point pattern into three dimensions by adding a 3rd co-ordinate to each point, the value of which is the 2-norm of the point, and performing the convex hull algorithm in 3 dimensions, then discarding that extra co-ordinate. I'm still not sure if this will get you the hourglass shape, but it's a step towards the right kind of idea.

Qaanol
The Cheshirest Catamount
Posts: 3060
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Finding points on a perimeter

MisterH wrote:For example - using the astronomical constellation of orion, all the stars except for the central one in the belt form the perimeter of an hourglass shape.

I do not think “all” means what you think it means.

Spoiler:
wee free kings

MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

### Re: Finding points on a perimeter

Qaanol wrote:
MisterH wrote:For example - using the astronomical constellation of orion, all the stars except for the central one in the belt form the perimeter of an hourglass shape.

I do not think “all” means what you think it means.

Spoiler:

You are quite right - shame on me.

(I blame light pollution though...)

Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Finding points on a perimeter

MisterH wrote:Given a cloud of co-ordinate points that contains more than 3 different positions, what is the most efficient method to work out which points form the perimeter?

For example - using the astronomical constellation of orion, all the stars except for the central one in the belt form the perimeter of an hourglass shape. How would you easily determine this for any other number/arrangement of stars?

Is it possible to work this out without using Pythagoras or Trigonometry?

You would have to start by saying which points you would want to remove. Specifically, why remove the central one from the belt, but keep the one furthest to the right? What is the mathematical reason for that? (BTW, not all three stars are in a line.)

phlip
Restorer of Worlds
Posts: 7557
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Finding points on a perimeter

Right... if you're going to want to analyse this mathematically, you're going to need to mathematically define why the shape you're looking for is this:
orion_hourglass.png (2.89 KiB) Viewed 1935 times
And not, say, one of these:
orion_convex.png (2.72 KiB) Viewed 1935 times
orion_tour.png (3.16 KiB) Viewed 1933 times
or any of a number of other possible shapes that can be made with those points.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

### Re: Finding points on a perimeter

This is a classic example of why I like discussing 'problems' such as this on here - I get both useful tips for solutions and insights into the logic of actual problem itself.

As for the three examples above, I still like the hourgalss one the best, which is fascinating since it is the most difficult to compute.

If you have less than three points, all of them are on the perimeter. If you select a 4th point, there is a x% chance it will be inside the perimeter of the other 3 (I cant prove if it's 50%, so am also open to discussion on that one!)

If there are limitations placed on the arrangement of the dots - ie, they are distributed within a circle or square region, or there is a limited number then different strategies can be applied to make determining the perimeter faster.

I don't really have a reason for asking the question in the first place - it was just something that I found interesting to think about.

Snark
Posts: 425
Joined: Mon Feb 27, 2012 3:22 pm UTC

### Re: Finding points on a perimeter

MisterH wrote:If you have less than three points, all of them are on the perimeter. If you select a 4th point, there is a x% chance it will be inside the perimeter of the other 3 (I cant prove if it's 50%, so am also open to discussion on that one!)

Are you talking about a specific collection of points, such as the stars in Orion from the Earth's perspective? Or any 4 points on an infinite plane?

In the first case, it's doubtful that the odds are exactly 50%, while in the second case, the odds are equal to 0.
Dashboard Confessional wrote:I want to give you whatever you need. What is it you need? Is it within me?

Avatar by Matt

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Finding points on a perimeter

MisterH wrote:As for the three examples above, I still like the hourgalss one the best, which is fascinating since it is the most difficult to compute.

I'm going to push back on the word "compute". It's not the process of computation that is the problem in all likelihood. The problem is that you have to ask a question whose answer is the hourglass shape., and to do that you need to understand why you prefer the hourglass shape. That's going to turn out to be a question of aesthetics rather than mathematics, although an important part of real math is bridging the interface like this.

To answer my own question, the reason we like the hourglass shape in this case is not because we like hourglasses but because I look at Qaanol's picture and, damn, I really can be convinced that it's a crude scatter plot of a guy with a raised sword in one hand and a bow in the other. So when we connect the dots in the constellations, we're doing so to share our own aesthetic biases. The reason for the larger "hull" in Qaanol's picture is because the IAU made the decision to partition the sky into 88 blocks so that if a new nova appeared tonight halfway between our stick figures of Orion and Taurus, we'd be able to say which neighborhood it was formally in.

Also, http://xkcd.com/1020/

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

### Re: Finding points on a perimeter

Tirian wrote:
MisterH wrote:As for the three examples above, I still like the hourgalss one the best, which is fascinating since it is the most difficult to compute.

I'm going to push back on the word "compute". It's not the process of computation that is the problem in all likelihood. The problem is that you have to ask a question whose answer is the hourglass shape., and to do that you need to understand why you prefer the hourglass shape. That's going to turn out to be a question of aesthetics rather than mathematics, although an important part of real math is bridging the interface like this.

I disagree slightly with this. In computational domains, there are very natural questions like this to ask that have little to do with aesthetics. For instance, how do you reconstruct the surface of a 3-D object from a point scan of its surface? How do you triangulate a non-convex domain? In some cases, you are in some way begging the question, but the questions you lead into are still very natural, mathematical, and computational in nature.

I believe, for instance, that you could obtain the hourglass shape computationally by taking the lifted convex hull of all points which are the vertex of an infinite area tile in the Voronoi tesselation of the point pattern. No guarantees, though, since I haven't tested it.

Edit: I roughly tested it; the belt stars are within finite-area tiles.

MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

### Re: Finding points on a perimeter

Interestingly, there is also a concave hull algorithm;