The paper makes three observations: 1) that preference is a partial ordering in one-dimension; 2) that a product, or a service, may be high-dimensional; consequently, and 3) transitivity, or its lack, results from choice of the direction for projection from high to low dimensions. The mass customization of cellular telephone designs gives the paper a context. The dimensions of the product space are: function, size, styling, color, etc. The medium for presentation (i.e., screen or paper), however, is necessarily two-dimensional (2-D). A criterion for projection is to preserve the information (such as, the similarity between the products, manifested as clusters, and the market opportunities, manifested as voids) from the high dimension. Drawing upon an analogy from the deformation mechanics of materials, the equilibrium conditions are formulated as distance and curvature. Distances give the clustering information; curvature gives the shape information. Projection is then seen as the process that minimizes the deformation in the projected geometry. The findings then become apparent. There are infinitely many ways to project. In most projections, intransitivity of preference results.

We consider the computation of an optimal workpiece orientation allowing the maximal number of surfaces to be machined in a single setup on a three-, four-, or five-axis numerically controlled machine. Assuming the use of a ball-end cutter, we establish the conditions under which a surface is machinable by the cutter aligned in a certain direction, without the cutter's being obstructed by portions of the same surface. The set of such directions is represented on the sphere as a convex region, called the visibility map of the surface. By using the Gaussian maps and the visibility maps of the surfaces on a component, we can formulate the optimal workpiece orientation problems as geometric problems on the sphere. These and related geometric problems include finding a densest hemisphere that contains the largest subset of a given set of spherical polygons, determining a great circle that separates a given set of spherical polygons, computing a great circle that bisects a given set of spherical polygons, and finding a great circle that intersects the largest or the smallest subset of a set of spherical polygons. We show how all possible ways of intersecting a set of n spherical polygons with v total number of vertices by a great circle can be computed in O ( vn log n ) time and represented as a spherical partition. By making use of this representation, we present efficient algorithms for solving the five geometric problems on the sphere.

By treating the floor plan of the building as a polygon, the authors study the problem of locating a camera for surveillance. A polygon P is point-visible if there exists a point x in P such that every other point in P is visible from x. If the polygon is point-visible then only one camera is needed. A visible edge corresponds to the wall on which the camera is to be mounted. While a given edge can be tested for visibility in time linear in the number of edges, there can be O(n) such edges. An O(n) time algorithm for finding all visible edges in a point-visible polygon is given. Specifically, it is shown that if the kernel of a simple polygon is nonempty, then all visible edges, whether completely, strongly, or weakly visible, can be found in O(n) time.>

The interrogation of spatial relations and properties of three-dimensional objects are often involved in applications programs for CAD/CADM and robotics. These interrogations can be expressed in terms of low-level data retrieval queries called access primitives (APs). A data structure is presented for storing spatial relations of three-dimensional objects such that the amount of storage is linearly proportional to the number of entities, and the response time for the APs is constant on the average. Linear storage for this data structure is the lower bound. The data structure is in the form of a symmetric graph. UsingE, the total number of edges of the object, as the unit, it is shown that the storage requirement of the symmetric data structure is 6E. By defining nine general data structure accessing primitives, it is shown that any local topological query can be answered in constant time, on the average.