******************************************************
The Kung et. al. Algorithm and Its Implementation
******************************************************

The algorithm developed  by Kung, Luccio and Preparata finds the
nondominated vectors (also called maximal  elements) of a set of
solutions V. This algorithm requires O(n lg n) comparisons for 
k = 2, and O(n (lg^{k-2} n)) comparisons for k >= 3, where n is 
the size of the input solution set and k is the dimension of the 
vectors.

For details of the algorithm, refer to the following paper:
   H.T. Kung, F. Luccio, and F.P. Preparata. On finding the 
   maxima of a set of vectors. Journal of the Association for 
   Computing Machinery, 22(4):469-476, 1975.



The algorithm was implemented following the description given by
Bentley in:
   Jon Louis Bentley, Multidimensional divide-and-conquer, 
   Communications of the ACM, 23 (1980), no. 4, 214-229.


******************************************************
How to compile the code and use the program
****************************************************************
The code is written in C++ and consists of the following files 
which are contained in the directory 'src':

VectorSet.h and VectorSet.cpp: Declaration and definition of a
class that store and maintains a set of vectors.

ndominated.h and ndominated.cpp: Declaration and definition of
the class that implements the Kung et. al.'s algorithm.

main.cpp: from this code is invoked the method that implements
the Kung et. al.'s algorithm.

To compile the code you need to write the command

$> g++ ndominated.cpp VectorSet.cpp main.cpp -o kung

to generate a executable named 'kung'.

The program have to be invoked by the command

$> kung <data set file> <dimension> <output file>

Where the data set file should contain a plain text file
with the input vector set, the next parameter is the 
dimension of the vectors in the data set and the output
file contains the nondominated vectors.

******************************************************
Examples
******************************************************

In the directory 'data' contain some files to test
the program. For example, the file deb3.dat contains a set
of 2-dimensional vectors resulting from the evaluation of
random values for the Deb's third problem. To finde the
nondominated vectors we have to use the command:

$> kung deb3.dat 2 NDS_Deb.dat

The file NDS_Deb.dat will contain the nondominated vectors.