3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Die Kolloidchemie des Tabakmosaikvirus

Ohne Zusammenfassung übersetzt von H. Kauffmann (Leipzig).     

Multi-Item Scheduling by Benders' Decomposition

Scheduling the production of several items requires the determination of production quantities in different periods in the presence of resource constraints. Several approximate and heuristic algorithms have been proposed to solve this problem. However, no method for finding an optimal solution has as yet been developed. It is shown that the problem may be solved advantageously using Benders' decomposition. The subproblem in Benders' decomposition is shown to be a transportation problem, and some strategies for solving the master problem are indicated. The paper concludes with a sample problem demonstrating the application of the method.     

Laser writing techniques for photomask fabrication using a femtosecond laser

Photomasks are the backbone of microfabrication industries. Currently they are fabricated by a lithographic process, which is very expensive and time consuming since it is a multi-step process. These issues can be addressed by fabricating photomasks by direct femtosecond laser writing, which is a single-step process and comparatively cheaper and faster than lithography. In this paper we discuss our investigations on the effect of two types of laser writing techniques, namely front- and rear-side laser writing, with regard to the feature size and the edge quality of a feature. It is proved conclusively that for the patterning of masks, front-side laser writing is a better technique than rear-side laser writing with regard to smaller feature size and better edge quality. Moreover the energy required for front-side laser writing is considerably lower than that for rear-side laser writing. Received: 22 May 2001 / Accepted: 14 September 2001 / Published online: 17 October 2001     

Distances between oriented curves in geometric modeling

We consider the choice of a functional to measure the distance between two parametric curves. We identify properties of such a distance functional that are important for geometric design. Several popular definitions of distance are examined, and new functionals are presented which satisfy the desired properties. This revised version was published online in August 2006 with corrections to the Cover Date.     

Multiple recurrence and infinite measure preserving odometers

A family of infinite measure preserving odometers is presented which exhibit examples ofp-recurrent but notp+1-recurrent ergodic transformations for everyp>1.