StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To find a point closest to M, we need to do binary elimination of points based on planar cuts. A little pre-processing of the input points is needed after which we can find a point closest to any given point M in O(lgn) time. </p> <ol> <li>Calculate (if not given) polar representation of points in (r,θ) format where r is the distance from center and θ is the angle from x-axis in the range (-180,180].</li> <li>Sort all N points in increasing order of their angle from x-axis.</li> </ol> <p>Note that simple binary search of a point closest to M will not work here, e.g., </p> <ul> <li>if the given points are sorted such that θ = (-130,-100,-90,-23,-15,0,2,14,170), then for a point M with θ = -170, binary search will give -130 (40 degrees away) as the closest point whereas 170 (20 degrees away) is the closest point to M. </li> <li>if we ignore the sign while sorting (thinking that it will produce correct output), our new sorted array will look like θ = (0,2,14,15,23,90,100,130,170), binary search for a point M with θ = -6 will yield the result should be either 2 or 14 whereas 0 is the closest point to M in this case.</li> </ul> <p>To perform the search operation using planar cuts, </p> <ul> <li>Find planar cut line passing through the center of circle and perpendicular to the line connecting the center of the circle with point M.</li> <li>Eliminate half of the circular plane [90+θ,-90+θ) or [-90+θ,90+θ) depending upon on in which half of the plane M lies.</li> <li>Make planar cuts parallel to the first cut and passing through the point in the middle of the previous plane and eliminate all points in the half of the plane farther from M until there are no points left in the nearer half of the plane, in which case eliminate the nearer half of the plane.</li> <li>Keep on cutting planes till we are left with one point. That point is the closest point to M. The total operation takes O(lgn) steps.</li> </ul> <p><img src="https://i.stack.imgur.com/3p4jB.png" alt="planar elimination"></p> <p>In case the data is skewed and not uniformly spread in the circle, we can optimize our planar cuts such that each cut passes through the median (based on angle) of those points which are left in the search operation. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload