1999 technical reports

CS-99-27
Title The Making of a Geometric Algebra Package in Matlab
Authors Stephen Mann, Leo Dorst, and Tim Bouma
Abstract In this paper, we describe our development of GABLE, a Matlab implementation of the Geometric Algebra based on cl_{p,q} (where p+q=3) and intended for tutorial purposes. Of particular note are the matrix representation of geometric objects, effective algorithms for this geometry (inversion, Meet and Join), and issues in efficiency and numerics.
Report The Making of a Geometric Algebra Package in Matlab (PDF) Compressed PostScript:
The Making of a Geometric Algebra Package in Matlab (GZIP)
CS-99-26
Title Stefy: Java Parser for HPSGs, Version 0.1
Authors Vlado Keselj
Abstract This document describes design and implementation of the system Stefy--a Java parser for Head-Driven Phrase Structure Grammars (HPSG). The parser is used in an Internet information retrieval system.
Report Stefy: Java Parser for HPSGs, Version 0.1 (PDF) Compressed PostScript:
Stefy: Java Parser for HPSGs, Version 0.1 (PS.Z)
CS-99-24
Title Health Informatics Education Working Paper
Authors H. D. Covvey and A. B. Pidduck
Date September 20, 1999
Report Health Informatics Education Working Paper (PDF)
CS-99-23
Title A Framework for Software Architecture Verification
Authors K. Lichtner, P. Alencar and D.D. Cowan
Date July 1999
Report A Framework for Software Architecture Verification (PS)
CS-99-22
Title An Abel ODE class generalizing known integrable classes
Authors E.S. Cheb-Terrab and A.D. Roche
Abstract A multi-parameter non-constant invariant Abel ODE class with the following remarkable features is presented. This one class is shown to generalize, that is, contain as particular cases, all the integrable classes presented by Abel, Liouville and Appell, as well as all those shown in Kamke's book and various other references. In addition, the class being presented includes other new and fully integrable subclasses, as well as the most general parameterized class we know of whose members can systematically be mapped into Riccati type ODEs. Finally, many integrable members of this class can be systematically mapped into an integrable member of a different class; leading in this way to new integrable classes from previously known ones.
Date Aug 24 1999
Comments This paper has been submitted to The European Journal of Applied Mathematics, August 1999
Report An Abel ODE class generalizing known integrable classes (DVI) An Abel ODE class generalizing known integrable classes (PDF) An Abel ODE class generalizing known integrable classes (ZIP)
CS-99-21
Title Abel ODEs: Equivalence and Integrable Classes
Authors E.S. Cheb-Terrab and A.D. Roche
Abstract A classification, according to invariant theory, of non-constant invariant Abel ODEs known as solvable and found in the literature is presented. A set of new integrable classes depending on one or no parameters, derived from the analysis of the works by Abel, Liouville and Appell, is also shown. Computer algebra routines were developed to solve any member of these classes by solving its related equivalence problem. The resulting library permits the systematic solving of Abel type ODEs in the Maple symbolic computing environment.
Date Aug 24 1999
Comments This paper has been submitted to Computer Physics Communications, July 1999
Report Abel ODEs: Equivalence and Integrable Classes (DVI) Abel ODEs: Equivalence and Integrable Classes (PDF) Abel ODEs: Equivalence and Integrable Classes (ZIP)
CS-99-20
Title Numeric and Symbolic Computation of Problems defined by Structured Linear Systems
Authors B. Beckermann and G. Labahn
Abstract This paper considers the problem of effective algorithms for some problems having structured coefficient matrices. Examples of such problems include rational approximation and rational interpolation. The corresponding coefficient matrices include Hankel, Toeplitz and Vandermonde-like matrices. Effective implies that the algorithms studied are suitable for implementation in either a numeric environment or else a symbolic environment.

The paper includes two algorithms for the computation of rational interpolants which are both effective in symbolic environments. The algorithms use arithmetic that is free of fractions but at the same time control the growth of coefficients during intermediate computations. One algorithm is a look-around procedure which computes along a path of closest normal points to an offdiagonal path while the second computes along an arbitrary path using a look-ahead strategy. Along an antidiagonal path the look-ahead recurrence is closely related to the Subresultant PRS algorithm for polynomial GCD computation. Both algorithms are an order of magnitude faster than alternate methods which are effective in symbolic environments.
Date August 1999
Report Numeric and Symbolic Computation of Problems defined by Structured Linear Systems (PDF)
CS-99-19
Title Large Independent Sets and Low-Degree Independent Sets in Planar Graphs in Linear Time
Authors T. Biedl
Abstract We study the problem of finding large independent sets in planar graphs in linear time. By modifying the traditional greedy-method, we show how to obtain an independent set of size at least 5/23 n in linear time. This falls short of the independent set of size 1/4 n, which is known to exist by the 4-color theorem, but is an improvement over the 1/5 n bound of the best known linear-time heuristic. We also study independent sets where vertices have bounded degree, and obtain for D >6 at least min { 5/23 n, (D-6)/(4D-18) n } independent vertices of degree < D in linear time.
Date July 1999
Comments A two-page abstract of this paper has been submitted at SODA'2000 (Symposium on Discrete Algorithms).
Report Large Independent Sets and Low-Degree Independent Sets in Planar Graphs in Linear Time (PDF) Compressed PostScript:
Large Independent Sets and Low-Degree Independent Sets in Planar Graphs in Linear Time (PS.Z)
CS-99-17
Title Characterization of Finite and One-Sided Infinite Fixed Points of Morphisms on Free Monoids
Authors J. Shallit and D. Hamm
Date July 1999
Report Characterization of Finite and One-Sided Infinite Fixed Points of Morphisms on Free Monoids (PDF) Compressed PostScript:Characterization of Finite and One-Sided Infinite Fixed Points of Morphisms on Free Monoids (PS.Z)
CS-99-16
Title An Evolutionary Approach to Structural Design Composition
Authors Paulo Alencar, Donald Cowan, Jing Dong, Carlos Lucena
Abstract One of the main goals of component-based software engineering (CBSE) is to enable automated assembly of software components, thus bringing greater quality and reliability, reducing development and test times, increasing productivity from multiple use of software components in the software development. A serious impediment for component assembly is due to the fact that the design and architectural assumptions that a reusable component makes about the structure of the application are in most cases implicit, lost or buried in complex implementation structures. In this paper we present an evolutionary approach to support the creation of reusable and changeable software architectures which focuses on the structural compositon of components at the design level. The architectural design information, captured by design patterns, is made explicit and represented in a declarative way, being packaged into tangible artifacts as building block design components in the development process. In this way, the declarative design component representations can be instantiated, adapted, assembled, maintained, and implemented. Furthermore, we can also use these representations to reason about properties related to the combination of design components. Our approach is illustrated through a case study involving various design patterns
Report An Evolutionary Approach to Structural Design Composition (PDF)
CS-99-15
Title Containment and Optimization of Object-Preserving Conjunctive Queries
Authors E.P.F. Chan and R. van der Meyden
Date February 1999
Report Containment and Optimization of Object-Preserving Conjunctive Queries (PDF) Compressed PostScript:
Containment and Optimization of Object-Preserving Conjunctive Queries (GZIP)
CS-99-14
Title Better Pasting Through Quasi-Interpolation
Authors B. Conrad
Abstract Hierarchical surface pasting, developed by Barghiel, Bartels and Forsey, is an interactive surface modelling technique that is used to add local detail to a tensor product B-spline surface without increasing the overall complexity of the original surface. Surface pasting approximates displacement mapped surfaces by placing additional tensor product surfaces, called features, on the base surface. The features may be scaled, rotated, and translated arbitrarily over the base surface, and the composite surface can be evaluated using relatively little computational power. Because the feature only approximates a displacement map, a surface produced using standard surface pasting often has noticeable gaps at the edges of the pasted feature. The severity of the surface discontinuities may be made as small as desired via knot insertion, but this can result in an unacceptable degradation in the performance of the modelling software.

Quasi-interpolation is an approximation method that approximates curves with spline curves to a high degree of accuracy. The approximation is constructed by computing coefficients that are used to weight samplings of the curve to be approximated. The Lyche-Schumaker quasi-interpolant uses coefficients that are inexpensive to compute and samplings that are relatively expensive to compute. I propose an improved surface pasting technique that uses quasi-interpolation to set the feature's boundary control vertices. For surface pasting it is necessary to have quasi-interpolants that reproduce position and derivatives at the endpoints of the curve to be approximated. In addition, as the feature surface is moved, the curve samplings must be recomputed, but the coefficients remain fixed. Therefore, I have developed a variation of the quasi-interpolant whose coefficients are expensive to compute, but whose samplings are relatively inexpensive to compute.

Surface pasting with quasi-interpolation produces features whose boundaries approximate the base surface to within the same tolerance as those produced by standard pasting, but with one third the boundary control vertices. The resulting feature has one ninth the total control vertices and can be constructed in approximately one tenth the time as with standard surface pasting.
Date May 1999
Report CS-99-14 (PDF) Compressed PostScript:
CS-99-14 (PS.Z)
CS-99-13
Title Cylindrical Surface Pasting
Authors S. Mann and T.P.-Y. Yeung
Abstract The idea of hierarchical modelling is that many surfaces have different levels of detail and for modelling purposes it is useful to interactively edit these surfaces at any level of detail. Detail can be added to tensor-product B-spline via knot insertion, but once the detail has been added the the surface can not be edited at a lower level of detail. Hierarchical B-splines were designed to allow for a type of knot insertion method that still admits editing the surface at any level of detail. However, the details can not be rotated, nor is it convenient to create a library of such details. Surface pasting is a generalization of hierarchical B-splines that allows for the creation of a feature library, and where the pasted features can be rotated and scaled, and translated across the base surface.

Cylindrical pasting is a parametric-blending method that creates a smooth transition surface between a pair of B-spline surfaces that do not originally intersect. This blending surface is a deformed cylinder, and its creation is based on the surface pasting composition method, which adds detailed features to base surfaces by means of an efficient displacement method. In cylindrical pasting, a transition cylinder can be pasted on a NUBS surface or onto a NUBS cylinder. A displacement scheme is used to locate the control points of the blending cylinder to achieve approximate $C^1$ continuity between the boundaries of the base surfaces and the edges of the cylinders.
Date May 1999
Report Cylindrical Surface Pasting (PDF) Compressed PostScript:
Cylindrical Surface Pasting (PS.Z)
CS-99-12
Title Multi-scale R-tree
Authors E.P.F. Chan and K.K.W. Chow
Date April 1999
Report Multi-scale R-tree (PDF) Compressed PostScript:
Multi-scale R-tree (PS.Z)
CS-99-09
Title Resizable Arrays in Optimal Time and Space
Authors A. Brodnik, S. Carlsson, E.D. Demaine, J.I. Munro and R. Sedgewick
Abstract We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l...l+n-1], of fixed-size elements, as elements are added to or removed from one or both ends. In addition to these operations, our data structures support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing the n current elements) is O(sqrt(n)) at any point in time. This is shown to be within a constant factor of optimal, even if there are no constraints on the time. If desired, each memory block can be made to have size 2^k - c for a specified constant c, and hence the scheme works effectively with the buddy system. The data structures can be used to solve a variety of problems with optimal bounds on time and extra storage. These include stacks, queues, randomized queues, priority queues, and deques.
Date September 2000
Comments A short version of this paper appears in Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99), edited by Frank Dehne, Arvind Gupta, Jvrg-R|diger Sack, and Roberto Tamassia, Lecture Notes in Computer Science, volume 1663, Vancouver, British Columbia, Canada, August 11-14, 1999, pages 37-48.
Report Resizable Arrays in Optimal Time and Space (PDF) Compressed PostScript:
Resizable Arrays in Optimal Time and Space (GZIP)
CS-99-05
Title Evaluating Tests for Input Stuck-at Faults in Word-Oriented Static Random-Access Memories
Authors P.R. Sidorowicz
Abstract An evaluation of well-known tests: Mats+, Mats++, March Y and March C- with respect to input stuck-at faults in a n-word by l-bit static CMOS random-access memory (SRAM) array is presented. First, an SRAM cell's behavior is analysed at the transistor-network, event-sequence, and finite-state machine (FSM) level. Then, an input stuck-at fault model for an SRAM is defined. We show that the word oriented extensions of the above-mentioned tests detect reliably at most (n+4l)/(2n+4l)*100% of faults in our fault model, which for large n constitutes roughly 50% of faults. We propose a DFT enhancement that would increase this coverage to 100%.

Keywords:CMOS, design for testability, fault modelling, March C-, March Y, Mats+, Mats++, SRAM, stuck-at faults, testing.
Date March 1999
Comments This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant No. OGP0000871.
Report Evaluating Tests for Input Stuck-at Faults in Word-Oriented Static Random-Access Memories (PDF) Compressed PostScript:
Evaluating Tests for Input Stuck-at Faults in Word-Oriented Static Random-Access Memories (PS.Z)
CS-99-04
Title Ununfoldable Polyhedra
Authors Marshall Bern (Xerox PARC)
Erik D. Demaine (University of Waterloo)
David Eppstein (University of California, Irvine)
Eric Kuo (MIT)
Abstract A well-studied problem is that of unfolding a convex polyhedron into a simple planar polygon. In this paper, we study the limits of unfoldability. We give an example of a polyhedron with convex faces that cannot be unfolded by cutting along its edges. We further show that such a polyhedron can indeed be unfolded if cuts are allowed to cross faces. Finally, we prove that "open'' polyhedra with convex faces may not be unfoldable no matter how they are cut.
Date August 1999
Comments This paper appears in the electronic proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15-18, 1999.

We are pursuing these problems further; please contact the authors if you make any progress.
Report Ununfoldable Polyhedra (PDF) Compressed PostScript:
Ununfoldable Polyhedra (PS.Z)
CS-99-03
Title Convexifying Monotone Polygons
Authors Therese C. Biedl (University of Waterloo)
Erik D. Demaine (University of Waterloo)
Sylvain Lazard (INRIA Lorraine)
Steven M. Robbins (McGill University)
Michael A. Soss (McGill University)
Abstract This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval. Our algorithm computes in O(n^2) time a sequence of O(n^2) moves, each of which rotates just four joints at once.
Date December 1999
Comments A version of this paper appears in Proceedings of the 10th Annual International
Symposium on Algorithms and Computation (ISAAC'99), Lecture Notes in Computer
Science, Springer-Verlag, volume 1741, Chennai, India, December 16-18, 1999,
pages 415-424.
Report Convexifying Monotone Polygons (PDF) Compressed PostScript:
Convexifying Monotone Polygons (PS.Z)
CS-99-02
Title Hardware Rendering with Bidirectional Reflectances
Authors J. Kautz and M. McCool
Abstract A separable decomposition of bidirectional reflectance distributions (BRDFs) is used to implement arbitrary reflectances from point sources on existing graphics hardware. Two-dimensional texture mapping and compositing operations are used to reconstruct samples of the BRDF at every pixel at inter- active rates.

A change of variables, the Gram-Schmidt halfangle/difference vector parameterization, improves separability in the case of near-specular BRDFs. Two decomposition algorithms are also presented. The singular value decomposition (SVD) minimizes RMS error. The normalized decomposition is fast, simple, and online, using no more space than what is required for the final representation.
Date February 1999
Comments There is a website which contains more information on this and other rendering projects in CGL.
Report Hardware Rendering with Bidirectional Reflectances (PDF) Hardware Rendering with Bidirectional Reflectances (README)
CS-99-01
Title Ptolemy: A Programmer's Manual
Authors K.W. Parker
Abstract Ptolemy is a prototype subsystem for the automatic set up of the numerical solution of Partial Differential Equations via sinc-collocation. Sinc collocation is a procedure for applying a change of variable such that spectral approximation is ultra efficient. As a result the setup process involves significant symbolic computation.
Date January 1999
Report Ptolemy: A Programmer's Manual (PDF) Compressed PostScript:
Ptolemy: A Programmer's Manual (GZIP)