In mathematics Nef polygons and Nef polyhedra are the sets of

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...

s and polyhedra which can be obtained from a finite set of

halfplane In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space. If the space is two-dimensional, then a half-space is called a half-plane (open or closed). A half-space in a one-dimensional sp ...

s ( halfspaces) by Boolean operations of set intersection and set complement. The objects are named after the

Swiss Swiss may refer to: * the adjectival form of Switzerland * Swiss people Places * Swiss, Missouri * Swiss, North Carolina *Swiss, West Virginia * Swiss, Wisconsin Other uses *Swiss-system tournament, in various games and sports *Swiss Internation ...

mathematician

Walter Nef Walter may refer to: People * Walter (name), both a surname and a given name * Little Walter, American blues harmonica player Marion Walter Jacobs (1930–1968) * Gunther (wrestler), Austrian professional wrestler and trainer Walter Hahn (born 19 ...

(1919–2013), who introduced them in his 1978 book on polyhedra. Since other Boolean operations, such as union or difference, may be expressed via intersection and complement operations, the sets of Nef polygons (polyhedra) are closed with respect to these operations as well. In addition, the class of Nef polyhedra is closed with respect to the topological operations of taking closure, interior, exterior, and boundary. Boolean operations, such as difference or intersection, may produce non-regular sets. However the class of Nef polyhedra is also closed with respect to the operation of

regularization Regularization may refer to: * Regularization (linguistics) * Regularization (mathematics) * Regularization (physics) * Regularization (solid modeling) * Regularization Law, an Israeli law intended to retroactively legalize settlements See also ...

Convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

s are a special subclass of Nef polyhedra, being the set of polyhedra which are the intersections of a finite set of half-planes.

Terminology

In the language of Nef polyhedra you can refer to various objects as 'faces' with different dimensions. What would normally be called a 'corner' or 'vertex' of a shape is called a 'face' with dimension of 0. An 'edge' or 'segment' is a face with dimension 1. A flat shape in 3D space, like a triangle, is called a face with dimension 2 – or a 'facet'. A shape in 3D space, like a cube, is called a face with dimension 3 – or a 'volume'.

Implementations

The

Computational Geometry Algorithms Library The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) ...

, or CGAL, represents Nef Polyhedra by using two main data structures. The first is a 'Sphere map' and the second is a 'Selective Nef Complex' (or SNC). The 'sphere map' stores information about the polyhedron by creating an imaginary sphere around each vertex, and painting it with various points and lines representing how the polyhedron divides space. The SNC basically stores and organizes the sphere maps. Each face contains a 'label' or 'mark' telling whether it is part of the object or not.

References

{{reflist , refs = {{cite document , citeseerx = 10.1.1.73.157 , title = Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, Optimized Implementation and Experiments , first1 = Peter , last1 = Hachenberger , first2 = Lutz , last2 = Kettner , first3 = Kurt , last3 = Mehlhorn , year = 2006 , publisher = Max Planck Institut Informatik , location = Saarbrücken, Germany Types of polygons Polyhedra