No description available.

No description available.

Computer Aided Design systems intended for three dimensional solid modelling have traditionally used geometric representations incompatible with established representations in computer vision. The utilization of object models built using these systems require a representation conversion before they can be used in automatic sensing systems. Considerable advantages follow from building a combined CAD and sensing system based on a common geometric model. For example, a library of objects can be built up and its models used in vision and touch sensing system integrated into an automated assembly line to 'discriminate between objects and determine- orientation and distance. This thesis studies a representation scheme, the dual spherical representation, useful in geometric modelling and machine recognition. We prove that the representation uniquely represents genus 0 polyhedra. We show by,example that our representation is not a strict dual of the vertex connectivity graph, and hence is not necessarily ambiguous. However, we have not been able to prove that the representation is unambiguous. An augmented dual spherical representation which is unique for general polyhedra is presented. This graph theoretic approach to polyhedra also results in an elegant method for decomposition of polyhedra into combinatorially convex parts. An algorithm implementation details and experimental results for recognition of polyhedra using a large field tactile sensor are given. A theorem relating the edges in the dual spherical representation and the edge under perspective projection is proved. Sensor fusion using visual and tactile sensory inputs is proposed to improve recognition rates. / Master of Science

Zhang, Hai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 106-109). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.5 / Chapter 2 --- Preliminaries --- p.13 / Chapter 2.1 --- Maxwell equations --- p.13 / Chapter 2.2 --- Reflection principle --- p.15 / Chapter 3 --- Scattering by General Polyhedral Obstacle --- p.19 / Chapter 3.1 --- Direct problem --- p.19 / Chapter 3.2 --- Inverse problem and statement of main results --- p.21 / Chapter 3.3 --- Proof of the main results --- p.22 / Chapter 3.3.1 --- Preliminaries --- p.23 / Chapter 3.3.2 --- Properties of perfect planes --- p.24 / Chapter 3.3.3 --- Proofs --- p.33 / Chapter 4 --- Scattering by Bi-periodic Polyhedral Grating (I) --- p.35 / Chapter 4.1 --- Direct problem --- p.36 / Chapter 4.2 --- Inverse problem and statement of main results --- p.38 / Chapter 4.3 --- Preliminaries --- p.39 / Chapter 4.4 --- Classification of unidentifiable periodic structures --- p.41 / Chapter 4.4.1 --- Observations and auxiliary tools --- p.41 / Chapter 4.4.2 --- First class of unidentifiable gratings --- p.45 / Chapter 4.4.3 --- Preparation for finding other classes of unidentifiable gratings --- p.47 / Chapter 4.4.4 --- A simple transformation --- p.52 / Chapter 4.4.5 --- Second class of unidentifiable gratings --- p.53 / Chapter 4.4.6 --- Third class of unidentifiable gratings --- p.58 / Chapter 4.4.7 --- Excluding the case with L --- p.61 / Chapter 4.4.8 --- Summary on all unidentifiable gratings --- p.65 / Chapter 4.5 --- Proof of Main results --- p.65 / Chapter 5 --- Scattering by Bi-periodic Polyhedral Grating (II) --- p.69 / Chapter 5.1 --- Preliminaries --- p.70 / Chapter 5.2 --- Classification of unidentifiable periodic structures --- p.72 / Chapter 5.2.1 --- First class of unidentifiable gratings --- p.72 / Chapter 5.2.2 --- Preparation for finding other classes of unidentifiable gratings --- p.73 / Chapter 5.2.3 --- Studying of the case L --- p.76 / Chapter 5.2.4 --- Study of the case with L --- p.89 / Chapter 5.2.5 --- Study of the case with L --- p.95 / Chapter 5.2.6 --- Summary on all unidentifiable gratings --- p.104 / Chapter 5.3 --- Unique determination of bi-periodic polyhedral grating --- p.104 / Bibliography --- p.106

Ph. D.

This research deals with a study of the polyhedral structure of three important combinatorial optimization problems, namely, the generalized upper bounding (GUS) constrained knapsack problem, the set partitioning problem, and the quadratic zero-one programming problem, and applies related techniques to solve a practical combinatorial naval defense problem. In Part I of this research effort, we present new results on the polyhedral structure of the foregoing combinatorial optimization problems. First, we characterize a new family of facets for the GUS constrained knapsack polytope. This family of facets is obtained by sequential and simultaneous lifting procedures of minimal GUS cover inequalities. Second, we develop a new family of cutting planes for the set partitioning polytope for deleting any fractional basic feasible solutions to its underlying linear programming relaxation. We also show that all the known classes of valid inequalities belong to this family of cutting planes, and hence, this provides a unifying framework for a broad class of such valid inequalities. Finally, we present a new class of facets for the boolean quadric polytope, obtained by applying a simultaneous lifting procedure. The strong valid inequalities developed in Part I, such as facets and cutting planes, can be implemented for obtaining exact and approximate solutions for various combinatorial optimization problems in the context of a branch-and-cut procedure. In particular, facets and valid cutting planes developed for the GUS constrained knapsack polytope and the set partitioning polytope can be directly used in generating tight linear programming relaxations for a certain scheduling polytope that arises from a combinatorial naval defense problem. Furthermore, these tight formulations are intended not only to develop exact solution algorithms, but also to design powerful heuristics that provide good quality solutions within a reasonable amount of computational effort. Accordingly, in Part ll of this dissertation, we present an application of such polyhedral results in order to construct effective approximate and exact algorithms for solving a naval defense problem. tn this problem, the objective is to schedule a set of illuminators in order to strike a given set of targets using surface-to-air missiles in naval battle-group engagement scenarios. The problem is conceptualized as a production floor shop scheduling problem of minimizing the total weighted flow time subject to time-window job availability and machine-downtime unavailability side constraints. A polynomial-time algorithm is developed for the case when ail the job processing times are equal (and unity without loss of generality) and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop three alternative formulations and analyze their relative strengths by comparing their respective linear programming relaxations. The special structures inherent in a particular strong zero-one integer programming model of the problem enable us to derive some classes of strong valid inequalities from the facets of the GUB constrained knapsack polytope and the set-packing polytope. Furthermore, these special structures enable us to construct several effective approximate and exact algorithms that provide solutions within specified tolerances of optimality, with an effort that admits real-time processing in the naval battle-group engagement scenario. Computational results are presented using suitable realistic test data. / Ph. D.