Next:
SR9 MINIMUM RECTANGLE
Up:
Compression and Representation
Previous:
SR7 MAXIMUM COMMON
SR8 M
AXIMUM
C
OMMON
P
OINT
S
ET
I
NSTANCE
: Positive integer
d
, collection
of
d
-dimensional point sets.
S
OLUTION
: A point set
S'
congruent to a subset of each set
in the collection.
M
EASURE
: Size, i.e. number of elements, of the common point set
S'
.
Good News:
Approximable within
, where
n
is the size of the smallest
[
3
].
Bad News:
Not approximable within
for some
[
3
].
Comment:
Transformation from M
AXIMUM
I
NDEPENDENT
S
ET
. The bad news is valid even if a small gap is allowed between corresponding points.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
of
d
-dimensional
point sets.
in the collection.
, where
n
is the size of the smallest
[
3
].
for some
[
3
].