these circles are all equal. Random geometric graphs, formed as unit disk graphs with randomly generated disk centres, have also been used as a model of percolation and various other phenomena. Computational complexity If one is given a collection of unit disks (or their centres) in a space of any fixed dimension, it is possible to construct the corresponding unit disk graph in linear time, by rounding the centres to nearby integer grid points, using a hash table to find all pairs of centres within constant distance of each other, and filtering the resulting list of pairs for the ones whose circles intersect. The ratio of the number of pairs considered by this algorithm to the number of edges in the eventual graph is a constant, giving the linear time bound. However, this constant grows exponentially as a function of the dimension. It is NP-hard (more specifically, complete for the existential theory of the reals) to determine whether a graph, given without geometry, can be represented as a unit disk graph. Additionally, it is impossible in polynomial time to output explicit coordinates of a unit disk graph representation: there exist unit disk graphs that require exponentially many bits of precision in any such representation. However, many important and difficult graph optimization problems such as maximum independent set, graph coloring, and minimum dominating set can be approximated efficiently by using the geometric structure of these graphs, and the maximum clique problem can be solved exactly for these graphs in polynomial time, given a disk representation. Even if a disk representation is not known, and an abstract graph is given as input, it is possible in polynomial time to produce either a maximum clique or a proof that the graph is not a unit disk graph, and to 3-approximate the optimum coloring by using a greedy coloring algorithm. See also Barrier resilience, an algorithmic problem of breaking cycles in unit disk graphs Indifference graph, a one-dimensional analogue of the unit disk graphs Penny graph, the unit disk graphs for which the disks can be tangent but not overlap (contact graph) Coin graph, the contact graph of (not necessarily unit-sized) disks Vietoris–Rips complex, a generalization of the unit disk graph that constructs higher-order topological spaces from unit distances in a metric space Unit distance graph, a graph formed by connecting points that are at distance exactly one rather than (as here) at most