Computer Simulation of a 3-D Sensing System with Structured Illumination

A computer simulation system of three-dimensional sensing with structured illumination is presented. It includes the generation of deformed fringe patterns from 3-D shapes and the reconstruction of 3-D shapes, conversely. Some experimental results of the deformed fringe pattern and the reconstructed object shapes are presented. We have also discussed the effect of some major system parameters on the measurement results and considered how to correct these parameters according to the measurement result of the standard plane. Using this simulation system, the major system parameters: environmental conditions, measurement accuracy and algorithm evaluation of the 3-D shape measurement system based on PMP, FTP, SPM, etc., can be researched. © 1997 Elsevier Science Ltd. All rights reserved.     

Minimizing the number of workers in a paced mixed-model assembly line

We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of m stations and executing n parts of k types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if $m=4$ and the workforce requirements are station independent, and present an Integer Linear Programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in k and polynomial in n algorithms for special cases with two part types or two stations are also given. Relations to the Bottleneck Traveling Salesman Problem and its generalizations are discussed.     

Geometric applications of posets

We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the n − k − 1 rectilinear farthest neighbors (or, equivalently, k nearest neighbors) to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0, report all the pairs of points that belong to S and are of rectilinear distance δ or more (less), covering k ≥ n/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number k ≥ n/2 decide whether a query rectangle contains k points or less.     

Extension of the generalized multipole technique to anisotropic medias

This paper presents an extension of the generalized multipole technique (GMT) for 2D anisotropic scatterers. New expansions similar to the Bessel multipole expansion are derived for arbitrary anisotropic media. Numerical simulations prove the accuracy and the rapid convergence of these expansions. As the results obtained are extremely accurate, this technique is most helpful for the evaluation of reference solutions and for the understanding of the physical interaction of light with arbitrary anisotropic media.     

A combinatorial approach to cartograms

A homeomorphism from ² to itself distorts metric quantities, such as distance and area. We describe an algorithm that constructs homeomorphisms with prescribed area distortion. Such homeomorphisms can be used to generate cartograms, which are geographic maps purposely distorted so their area distributions reflects a variable different from area, as for example population density. The algorithm generates the homeomorphism through a sequence of local piecewise linear homeomorphic changes. Sample results produced by the preliminary implementation of the method are included.     

Shortest paths in piecewise continuous time-dependent networks

We consider a shortest path problem, where the travel times on the arcs may vary with time and waiting at any node is allowed. Simple adaptations of the Dijkstra algorithm may fail to solve the problem, when discontinuities exist. We propose a new Dijkstra-like algorithm that overcomes these difficulties.     

An efficient cost scaling algorithm for the assignment problem

The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.This author's research was supported by the above-mentioned ONR and NSF grants.     

A class of rank-two ellipsoid algorithms for convex programming

In this paper, we develop a method for constructing minimum volume ellipsoids containing a wedge-shaped subset of a given ellipsoid. This construction yields a class of ellipsoid algorithms for convex programming that use rank-two update formulae. Research supported by the National Science Foundation, Grant No. MC582-01790.     

Hybrid grids and the Homing Robot

In their paper (Inform. Process. Lett. 77 (2001) 261), Wongngamnit and Angluin introduced a memory-efficient robot, called the Homing Robot, which localizes in an occupancy grid. We present a more general class of grids called hybrid grids, and establish the least upper bound for the number of moves the robot takes to localize. We also state analogous results for a hexagonal tiling.     

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.