Table of

Definition: A Nefpolyhedron in dimension d is a point set P⊆ℜ^{d} generated from a finite number of open halfspaces by set complement and set intersection operations [Nef78].
This definition emcompasses many definitions of linearly bounded complexes and has the outstanding properties that it is closed under boolean operations and can represent nonmanifold situations, that it supports faces of different dimensions at the same time and unbounded faces, and that can distinguish between open and closed sets.
We, i.e., Peter Hachenberger and Lutz Kettner, continued the work of Michael Seel to bring Nef polyhedra as defined by the Swiss mathematician Walter Nef into CGAL. While Michael Seel provided planar Nef polyhedra, we implemented Nef polyhedra in 3dimensional space. The implementation was first released as part of CGAL 3.1 in December 2004. Our implementation follows the design spirit of CGAL and the Exact Geometric Computing paradigm. Our implementation is complete (it handles all degenerate cases) and correct (it does not suffer from rounding problems of floating point arithmetic), and it is efficient, which we document in the paper [2] below and with the corresponding data and results published on this page.
2 
Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments. Peter Hachenberger and Lutz Kettner. In: Proc. of 2005 ACM Symposium on Solid and Physical Modeling (SPM), Cambridge, MA. pp. 163174, June, 2005. © ACM 2005. [Abstract] [PDF] [PostScript] 
1 
Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation. Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn, and Michael Seel. In: Proc. of the 11th Annu. European Sympos. Algorithms (ESA'03), Budapest, Hungary. LNCS 2832, Springer, pp. 654666, September, 2003. [Abstract] [PDF] [PostScript] 
For each of the six experiments we give a short description, the complete timing results, and the complete input data sets. An addition to the short description of the experiment we refer to our paper [2] for more details. The timing results are shown in a graph and also available for download in the tabular .sus format of the ExpLab tools described here. The input data sets are given in the custom .nef3 format of our implementation and, where applicable, in the .sat format for the ACIS comparisons. In addition, since the data sets can be quit large, we provide also the CGAL generator program for these data sets and, where applicable, the ACIS Scheme program.