What about limits? There could be different approaches depending on number of points etc...

If k is small (say, constant), then we can build a higher order Voronoi diagram in time , and the reduce our problem to the planar point location problem. So, we get a data structure with preprocessing time , space O(k(n - k)), and query time .

k-nearest neighbor of a point in 2-D co-ordinate system.

By the way, which distance between points do you mean? :-)

or |x| + |y| ?

Answer to one query is "chain of the K nearest neighbors of point number i", rigth?

You say n, k, q ≤ 10⁵. Size of answer is k × q. It is 10¹⁰. Maybe just q × k ≤ 10⁵?

UPD

If constraints really are k × q ≤ 10⁵, KD-tree works good for random sets of points.

About KD trees: wiki, some implementation, my implementation for acm.timus.ru task.1369

You can do this using KD tree. Basically, if you know KD tree nearest neighbor query, to transform it into k-nearest, just store all the points in a priority queue while traversing.

It's O(k log(k) log(n)) on average, O(k log(k) sqrt(n)) on worst. For proofs, look at the cited references in wikipedia.

Short implementation of 2D KNN in C++ using KD tree below, tested.

EDIT: build is O(n log n), not O(2n) EDIT 2: I tested this on Kattis, with k=2. Unfortunately, I can't find online judges with KNN to test with. If you know some problems, I would appreciate a reply.

// 2D point object
struct point {
	double x, y;
	point(double x = 0, double y = 0): x(x), y(y) {}	
};

// the "hyperplane split", use comparators for all dimensions
bool cmpx(const point& a, const point& b) {return a.x < b.x;}
bool cmpy(const point& a, const point& b) {return a.y < b.y;}

struct kdtree {
	point *tree;
	int n;
	// constructor
	kdtree(point p[], int n): tree(new point[n]), n(n) {
		copy(p, p + n, tree);
		build(0, n, false);
	}
	// destructor
	~kdtree() {delete[] tree;}
	// k-nearest neighbor query, O(k log(k) log(n)) on average
	vector<point> query(double x, double y, int k = 1) {
		perform_query(x, y, k, 0, n, false); // recurse
		vector<point> points;
		while (!pq.empty()) { // collect points
			points.push_back(*pq.top().second);
			pq.pop();
		}
		reverse(points.begin(), points.end());
		return points;
	}
private:
	// build is O(n log n) using divide and conquer
	void build(int L, int R, bool dvx) {
		if (L >= R) return;
		int M = (L + R) / 2;
		// get median in O(n), split x-coordinate if dvx is true
		nth_element(tree+L, tree+M, tree+R, dvx?cmpx:cmpy);
		build(L, M, !dvx); build(M+1, R, !dvx);
	}

	// priority queue for KNN, keep the K nearest
	priority_queue<pair<double, point*> > pq;
	void perform_query(double x, double y, int k, int L, int R, bool dvx) {
		if (L >= R) return;
		int M = (L + R) / 2;
		double dx = x - tree[M].x;
		double dy = y - tree[M].y;
		double delta = dvx ? dx : dy;
		double dist = dx * dx + dy * dy;
		// if point is nearer to the kth farthest, put point in queue
		if (pq.size() < k || dist < pq.top().first) {
			pq.push(make_pair(dist, &tree[M]));
			if (pq.size() > k) pq.pop(); // keep k elements only
		}
		int nearL = L, nearR = M, farL = M + 1, farR = R;
		if (delta > 0) { // right is nearer
			swap(nearL, farL);
			swap(nearR, farR);
		}
                // query the nearer child
		perform_query(x, y, k, nearL, nearR, !dvx);

		if (pq.size() < k || delta * delta < pq.top().first)
                        // query the farther child if there might be candidates
			perform_query(x, y, k, farL, farR, !dvx);
	}
};