Hacker News Reader

Comment by thejteam | Hacker News Reader

That was what I thought it would be at first as well. My definition of "most" concave: pick two points at random in the state. What is the probability the segment connecting them leaves the state? In this case the hard part is defining what to do about water. As an example, I live in Maryland. It is easily the most concave if you don't treat the Chesapeake Bay as part of the state. If you do, not quite as concave. See maps in the link for the shape of MD if you are not familiar with it.

View on HN

I was going to go with "Divide the land area of a state by the area of its convex hull. Which is the lowest percentage?"

Yeah that was what I was expecting they'd do also.

Maybe you'd want to compute the convex hull on a per-connected-component basis, though, to avoid allowing small islands to have undue influence.

Either that, or say that any area of sea within its convex hull gets treated as part of the state's area. This approach differs in that it special-cases sea over other kinds of land.

Would you not get the mean height above sea level of all points along the border and divide that by the mean height above sea level of the entire state (which I guess is really an average of some sampling of points)?

For that suggestion I was just considering it a two-dimensional problem with a "sea or not sea" distinction, not using heights above sea level.

My first thought was to go with the length of the state's boundary that is on the convex hull divided by the length of the whole boundary.

So...we've got at least 3 ways so far to assign a measure of convexity/concavity to a state, and they give quite different results.

For instance, your method and the method in the comment you responded to both would assign a low concavity to a state that is almost a square, except that the boundary has a high frequency, low amplitude sawtooth pattern imposed on it. Mine would score that has a very high concavity.

I was interested in this and did a very quick google search. Measuring concavity/convexity of a generic 2D surface object doesn't seem to be a very common operation. The one reference I found seems to do what you describe:

http://www.ncbi.nlm.nih.gov/pubmed/7945702

Although I don't have PubMed access so I can't be sure.

This is an interesting problem.

I chose the "random points" method because it seemed easier to me to get an approximate answer for a generic shape rather than try to figure out areas. Lengths didn't occur to me though and seems interesting, although the shape you describe doesn't "feel" concave to me.

Maths challenge:

I wonder if you could prove this "probability of a random line segment violating convexity" definition equivalent to something given in terms of a ratio of different areas like the area to convex hull area suggestion below.

If you're going to include water I think Hawaii may have Maryland beat. Maybe even Alaska?

I forgot about islands...

But I don't really think of Hawaii as "concave". So I'm going to refine my definition to only allow the points to be chosen in connected areas.

> So I'm going to refine my definition to only allow the points to be chosen in connected areas.

Are two areas considered connected if they cross a river, once?

Reply on news.ycombinator.com