MAXIMUM COMMON POINT SET

• INSTANCE: Positive integer d, collection $S_1, \ldots, S_k$ of d-dimensional point sets.

• SOLUTION: A point set S' congruent to a subset of each set $S_i$ in the collection.

• MEASURE: Size, i.e. number of elements, of the common point set S'.

  
  

• Good News: Approximable within $O(n/\log n)$, where n is the size of the smallest $S_i$ [6].

• Bad News: Not approximable within $n^\varepsilon$ for some $\varepsilon >0$ [6].

• Comment: Transformation from MAXIMUM INDEPENDENT SET. The bad news is valid even if a small gap is allowed between corresponding points.