2025/06/27 by Tkachenko, Anastasiia, Wang, Haitao · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.21926
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(n7/3+o(1)) time. We show that the problem can be solved in O(n log n + n K4/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(n15/7+o(1))= O(n2.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(n2log n) time (deterministic) algorithm for this special case.