Computing maximum cliques in unit disk graphs

Given a set P of n points in the plane, the unit-disk graph G ( P ) is a graph with P as its vertex set such that two points of P have an edge if their Euclidean distance is at most 1. We consider the problem of computing a maximum clique in G ( P ) . The previously best algorithm for the problem runs in O ( n 7 / 3 + o ( 1 ) ) time. We show that the problem can be solved in O ( n log ⁡ n + n K 4 / 3 + o ( 1 ) ) time, where K is the maximum clique size. The algorithm is faster than the previous one when K = o ( n ) . In addition, if P is in convex position, we give a randomized algorithm that runs in O ( n 15 / 7 + o ( 1 ) ) = O ( n 2.143 ) worst-case time and the algorithm can compute a maximum clique with high probability. For points in convex position, one special case we solve is when a point in the maximum clique is given; we present an O ( n 2 log ⁡ n ) time (deterministic) algorithm for this special case.