All Nearest Neighbors

Given a set P of points in the plane, design an algorithm to find the nearest neighbor for each point in P.

Solution:

This problem can be solved by plane-sweep technique. We show how to find nearest neighbors to the left. Finding nearest neighbors to the right is similar. Sort all points in increasing x-coordinate and scan from left to right. For the sweep line L, we associate a set S of points in P that have nearest neighbors on L. Order the points in S in decreasing y-coordinate. We know that a circle passing through any consecutive 3 points in S, its center must lie on the right of L. Otherwise, the middl point should not be in S. Thus, for a newly processed point p, we can insert p to S properly and test whether p is closer to its neighbors in S. Then, we find the circle formed by p‘s neighbors to remove points from S. The total complexity is O(n lg n).

Reference: Stackoverflow

Klaus Hinrichs, Jurg Nievergelt, Peter Schorn, “An all-round sweep algorithm for 2-dimensional nearest-neighbor problems,” Acta Informatica 1992, Volume 29, Issue 4, pp 383-394

Advertisements

Minimum Isothetic Square Enclosing k points

Given a set P of n points in a bounded plane and an positive integer k < n, design an algorithm to find the Minimum isothetic square that contains at least k points.

Solution:

Consider the decision problem as follows: for a given length L, is there a square with side length L containing at least k points. This problem is equal to put n squares with side length L centered at each point and determine the depth of an arrangement of boxes, which can be solved in O(n lg n) time. The optimization problem can be solved by applying binary search on O(n^2) possible choices of lengths. Thus, the problem can be solved in O(n \lg^2 n).

David Eppstein, Jeff Erickson, “Iterated nearest neighbors and finding minimal polytopes,” Discrete & Computational Geometry 1994, Volume 11, Issue 1, pp 321-350

Smallest isothetic rectangle enclosing k points can be found in O(n + k(n-k)^2).

Michael Segal, Klara Kedem, “Enclosing k points in the smallest axis parallel rectangle,” Information Processing Letters Volume 65, Issue 2, 29 January 1998, Pages 95–99

Smallest square/rectangle enclosing k points can be found in O(n^2 \lg n + nk(n-k)(n-k + \lg k)).

Sandip Das, Partha P. Goswami, Subhas C. Nandy, “Smallest k-point enclosing rectangle and square of arbitrary orientation,” Information Processing Letters Volume 94, Issue 6, 30 June 2005, Pages 259–266

Smallest circle enclosing k points can be found in O(nk).

Sariel Har-Peled, Soham Mazumdar, “Fast Algorithms for Computing the Smallest k-Enclosing Circle,” Algorithmica March 2005, Volume 41, Issue 3, pp 147-157

Reference: Stackoverflow