International Journal of Computational Geometry & Applications

We present some computational methods in a particular case of mixing and separation theory, as an application of classical results in the field of computational geometry. Our aim is the production of some given mixtures by mixing parts of basic products. In the geometrical approach we use, products or mixtures are characterized by vectors and the mixing process by vector sums, in the vector space of physico-chemical species. The feasibility of a mixture is viewed as a point-inclusion in the convex set of mixtures which is a zonotope associated with basic mixtures. This paper is concerned with binary mixtures characterized by two species. The geometrical approach leads to plane geometry problems and gives complete solutions to the optimal fabrication of a mixture, as well as to the fabrication of a sequence of several mixtures. Using the framework of computational geometry, we present efficient algorithms for solving the main problems related to the management of binary mixtures.

We consider a random collection of n line segments, in which the segments are independently drawn by picking the midpoint according to a given distribution in the plane, by picking a uniformly distributed random direction, and by adding an independently sampled segment length. We study the expected behavior of the number of intersections as a function of n, the lengths of the line segments, and the distribution of the midpoints. This includes a universally applicable law of large numbers.

The scope of this work is Geometric Modeling. We study the representation and the construction of subdivisions of quasi-manifolds, using a topology-based approach. Quasi-manifolds are here defined as a subset of pseudo-manifolds, which are well-known objects in Algebraic Topology.

N-dimensional generalized maps (resp. n-dimensional maps) are combinatorial models defined for representing the topology of subdivisions of orientable or non-orientable quasi-manifolds with or without boundaries (resp. orientable quasi-manifolds without boundaries).

In this paper, we define the models, main related notions and properties as cells, boundaries, duality, orientability, Euler characteristic. Basic operations are proposed for handling the models.

We also show the correspondence between the combinatorial models and combinatorial cellular quasi-manifolds, here defined as combinatorial simplicial quasi-manifolds to which a structure into cells is added. This correspondence establishes that the models are rigorous and unambiguous ones.

Moreover, the definitions of the models and the related notions and operations are quite simple, and they can be easily implemented and used in geometric modellers.

We present a survey of the hidden surface removal literature, focusing on object-space algorithms. We give a brief definition and history of the problem, followed by a discussion of problems and algorithms associated with the priority ordering of faces. We go on to examine object-space algorithms in order of increasing object complexity: xy-parallel rectangles, ordered triangles, c-oriented faces, c-oriented polyhedra, polyhedral terrains, and general polyhedra. We also review recent work on merging visibility maps and moving viewpoints. Finally, we present a list of open problems.

Open problems from the Tenth ACM Symposium on Computational Geometry and the Sixth Canadian Conference on Computational Geometry listed tersely.