Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
Hey tye,

You know I -love- to nitpick, discuss and generally rant on alogrithms (which never looks spelt correctly). So don't take anything below as an attack on you :) (which I know you aren't, I'm just saving myself from --'s! lol).

Anyway the nearest neighbor problem can be an interesting one! There are two methods I'd like to mention for their various merits.

The first is to use a Voronoi diagram. Voronoi diagrams just creates a list of connected verti that represent the furthest distance between two points. The simplest way to implement the construction of one of these, is to start with two items and draw a perpendicular line at the midpoint of the line they create. Now add an additional point randomly and follow the same method.

The advantage here, is construction takes about n*log n time (though with random, you don't get nearly as good of performance as some other methods available, which are still n*log n though). Once constructed, the Voronoi diagram gives you lots of fun info. To determine the nearest neighbor, you simply have to find which 'cell' (enclosing vertex lines) you're in. To determine a point of maximal distance, look at the verti themselves.

The other method is fairly simple. It's like your band-width method in approach. You keep the points in sorted order. You then find the closest two points left and right of the target. Find the distance between these two points and the target. Take the smaller and construct a square bounding box around the target of width twice that distance. Now linearly search through all points within that space. Quick, simple, and it works well with most data. (btw keeping points in sorted order makes for the fast lookup).

I don't like the band-width method because it's just as complicated as the above method to get the correct answer (you don't get the correct answer just looking in that one band, you have to look in several most of the time), and not much faster except under weird circumstances. That is, spliting into band-widths helps decrease some of the search time, but it is also a more crude search since it isn't as accurate, and so you waste time removing the cruft returned (or blinding processing extra points).

Welp, I'm ranting, tired and allergic.

Ciao,
Gryn :)


In reply to Re: (tye)Re: Algorythym for searching closest neighbor by gryng
in thread Algorythym for searching closest neighbor by belize

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chilling in the Monastery: (4)
As of 2024-03-29 02:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found