On Finding Maximum-Cardinality Symmetric

Peter Braß
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: brass@inf.fu-berlin.de

Report B-00-21
December 2000

In this paper we study the complexity of the problem of finding a symmetric subset of maximum cardinality among n point in the plane, or in three-dimensional space, and some related problems like the largest repetive or k-repetive subsets. For the maxium-cardinality symmetric subset problem in the plane we obtain an algorithm of complexity 0(n^2+ 1/3 log n).
Get the report here or by anonymous ftp:
Server: ftp.inf.fu-berlin.de
File:   pub/reports/tr-b-00-21.ps.gz