Next: MINIMUM RECTANGLE COVER Up: Compression and Representation Previous: MAXIMUM COMMON SUBTREE Index

### MAXIMUM COMMON POINT SET

- INSTANCE: Positive integer d, collection of d-dimensional point sets.

- SOLUTION: A point set S' congruent to a subset of each set Si in the collection.

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

- Good News: Approximable within , where n is the size of the smallest Si [6].

- Bad News: Not approximable within for some [6].

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