The minimum clique partition (MCP) problem is that of partitioning the vertex
set of a given graph into a minimum number of cliques. Given $n$ points in the
plane, the corresponding unit disk graph (UDG) has these points as vertices,
and edges connecting points at distance at most~1. MCP in unit disk graphs is
known to be NP-hard and several constant factor approximations are known,
including a recent PTAS. We present two improved approximation algorithms for
minimum clique partition in unit disk graphs:

(I) A polynomial time approximation scheme (PTAS) running in time
$n^{O(1/\eps^2)}$. This improves on a previous PTAS with $n^{O(1/\eps^4)}$
running time \cite{PS09}.

(II) A randomized quadratic-time algorithm with approximation ratio 2.16.
This improves on a ratio 3 algorithm with $O(n^2)$ running time \cite{CFFP04}.