Tight Convex Hulls: Who Are My Neighbors?
In one of my research projects we have a set of points on a two dimensional plane that when given a single point from that set we want to be able to know who its "neighbors" are. For our work we have the mesonet stations spread across the state of Okalhoma and we want to be able to select the neighboring stations. There are a couple of methods that are intuitive but require setting a parameter, something I'm not fond of. Also we have the concept of multiple levels of neighbors, so my first neighbors, my second neighbors and so on.
The first possible method is to say all my first neighbors are the stations within X miles of me. Next, my second neighbors are the additional stations that wre within 2X miles of me, then 3X for third and so on. My qualm with this method is the selection of the appropriate X. Since the stations are not uniformly distributed across the state it might require different values of X for different stations.
The second method is to choose the N closest stations and they become my first neighbors, then my second neighbors are the additional stations that are in the 2N closest stations and so on. Again this has the issue of requiring that the parameter N be chosen.
Not satisfied with any of these I developed yet a third method that uses the idea of convex hulls. A convex hull can be easily visualized by imagining a peg board whith a bunch of pegs random distributed across it. If you then take a rubber band and stretch it around all the outer most pegs the line it traces will the convex hull of those pegs. Now the convex hull of all stations would included everything and hence wouldn't be very useful because every station would be my first neighbor and we want multiple layers of neighbors.
At first guess we might say, take all the stations and form a convex hull. Then remove the station farthest away from me and reform the convex hull. Repeat this process until removing one more peg would mean I'm no longer inside the hull. By doing this we are making the smallest convext hull that contains us. This hull forms my first neighbors. Then we can start over and this time remove stations until it causes either me or one of my first neighbors to no longer be covered by the hull, then those stations in this bigger convex hull will form my second neighbors. This runs into the problem that frequently the smallest convex hull formed in this manner will be a triangle. And a station having generally three neighbors in each layer isn't very appealing to us.
Enter my new constraint on the hull. Instead of find the smallest hull containing a set of stations we want to find what i've termed the largest tight convex hull. The largest tight convex hull is a convex hull that given an initial set of points and a center point, that adding the next closest point to the center causes the convex hull to include a point that was not in the initial set.