2000 technical reports

CS-2000-22
Title	Finding Patterns in Biological Sequences
Authors	B. Brejova, C. DiMarco, T. Vinar, S.R. Hildalgo, G. Holguin and C. Patten
Abstract	In this report we provide an overview of known techniques for discovery of patterns of biological sequences (DNA and proteins). We also provide biological motivation, and methods of biological verification of such patterns. Finally we list publicly available tools and databases for pattern discovery.
Date	December 2000
Report	Finding Patterns in Biological Sequences (PDF)

CS-2000-21
Title	Efficient Evaluation of Subdivision Surfaces
Authors	E. Hall
Abstract	New algorithms and data representations are introduced for the efficient evaluation of subdivision surfaces. The first algorithm presented uses a data structure based on strips of quadrilaterals to implicitly define adjacency information for mesh faces through vertex order. This approach reduces memory requirements by a constant factor in the average case and allows for a fast evaluation scheme. The next algorithm extends this idea for use in a hardware evaluation setting. A simple API and protocol for transmitting quadstrips with adjacency information to hardware is defined. An online algorithm requiring only small constant storage for a given recursion depth is then used to subdivide each strip.
Date	December 2000
Report	Efficient Evaluation of Subdivision Surfaces (PDF)			Compressed PostScript: Efficient Evaluation of Subdivision Surfaces (GZIP)

CS-2000-20
Title	The Verification of Hypermedia Design Composition
Authors	Jing Dong, Paulo S. C. Alencar, Donald D. Cowan
Abstract	Developing large-scale software systems by integrating software components becomes important practice due to the increasing complexity and size of these software applications. However, the unexpected interactions among the components of software systems are often the cause of failure of component-based systems. The analysis of the properties of the components and their compositons allows us to detect these interactions and correct the compositon errors. Discovering composition errors early in the development process can save considerable effort of fixing them downstream. This paper introduces a rigorous analysis approach based on model checking to software design compositon. In particular, the analysis goal is to verify whether properties related to structural, behavioral and evolutionary aspects of the design component specifications hold when these components are integrated. We illustrate our approach with a hypermedia case study, showing how to represent, instantiate and integrate design components, and how to find design compositon errors using model checking techniques.
Report	The Verification of Hypermedia Design Composition (PDF)

CS-2000-19
Title	Solving Inverse Kinematics Constraint Problems for Highly Articulated Models
Authors	T.K. Ge
Abstract	Given a goal position for the end effector of a highly articulated model, the task of finding the angles for each joint in the model to achieve the goal is an inverse kinematics problem. Redundancy of the degrees of freedom (DOF) can be used to meet secondary tasks such as obstacle avoidance. Solutions to redundant inverse kinematic problems are well developed. The most common technique is to differentiate the nonlinear equations and solve a linear Jacobian matrix system. The pseudoinverse of the Jacobian can be calculated via a singular value decomposition (SVD). The general SVD algorithm reduces a given matrix first to a bidiagonal form then diagonalizes it. The iterative Givens rotations method can also be used in our case, since the new Jacobian is a perturbation of previous one. Secondary tasks can be easily added to this matrix system, but it is nontrivial to generalize this problem to a highly redundant model in a complex environment in the computer graphics context. For this thesis, I implemented and compared several SVD techniques; and found that both general and iterative algorithms are of linear time-complexity when solving a three-row matrix. I also programmed and compared different methods to avoid one or multiple obstacles.
Date	December 2000
Report	Compressed MPEG: Solving Inverse Kinematics Constraint Problems for Highly Articulated Models (GZIP)	Solving Inverse Kinematics Constraint Problems for Highly Articulated Models (PDF)

CS-2000-18
Authors	A. An
Report	No report

CS-2000-17
Title	Linear Reductions of Maximum Matching
Authors	T.C. Biedl
Abstract	In this paper, we give linear reductions from maximum matching to maximum matching in a special graph class, such as 3-regular graphs, or biconnected graphs with maximum degree 3. We also reduce maximum matching in planar graphs to maximum matching in triangulations with maximum degree 9. Our results imply that rather than searching for faster maximum matching algorithms general, one should concentrate on maximum matching algorithms for these special graph classes.
Date	November 2000
Comments	The paper will appear at SODA 2001 (Symposium on Discrete Algorithms), and has been submitted to SIAM Journal on Computing.
Report	Linear Reductions of Maximum Matching (PDF)			Compressed PostScript: Linear Reductions of Maximum Matching (PS.Z)

CS-2000-16
Authors	P. Ward and D.J. Taylor
Date	number issued October 4, 2000
Report	Only available in printed format

CS-2000-15
Title	The Direct Manipulation of Pasted Surfaces
Authors	M. Ma
Abstract	Surface pasting is a method for creating complex composite surfaces by adding local detail or feature surfaces to a base surface. Previous surface pasting editors enabled users to paste, translate, rotate, and resize feature surfaces, but none allowed users to directly manipulate a surface in the pasting hierarchy. In this thesis, I propose a multiresolution direct manipulation technique that allows the user to pick a point on a surface and move it to a new location and have the shape of the surface change appropriately. My method provides a more flexible modelling paradigm for pasted surfaces by allowing the user to pick both the new location of the selected point and the granularity of the change that is applied to the composite surface.
Date	September 2000
Comments	CS-2000-15.mpg.gz - gzipped MPEG demonstrating some of the direct manipulation techniques CS-2000-15.mov.gz - gzipped QuickTime movie demonstrating some of the direct manipulation techniques
Report	Compressed QuickTime movie: The Direct Manipulation of Pasted Surfaces (GZIP)	Compressed MPEG: The Direct Manipulation of Pasted Surfaces (GZIP)	The Direct Manipulation of Pasted Surfaces (PDF)	Compressed PostScript: The Direct Manipulation of Pasted Surfaces (GZIP)

CS-2000-14
Title	SMASH: A Next-Generation API for Programmable Graphics Accelerators
Authors	M. McCool
Date	July 2000
Report	SMASH: A Next-Generation API for Programmable Graphics Accelerators (PDF)

CS-2000-13
Title	Cross-coloring: improving the technique by Kolmogorov and Barzdin
Authors	T. Biedl and T. Chan
Abstract	In this paper, we study how to color crosses, i.e., pairs of rows and columns in a grid, such that any two overlapping crosses have a different color. We show that this problem can be solved by computing an edge-coloring in a bipartite graph. Using this result we reduce significantly the time complexity and the volume bounds of algorithms for three-dimensional orthogonal graph drawing that are based on the technique of Kolmogorov and Barzdin.
Date	June 2000
Comments	The paper has been submitted to Graph Drawing 2000.
Report	Cross-coloring: improving the technique by Kolmogorov and Barzdin (PDF)			Compressed PostScript: Cross-coloring: improving the technique by Kolmogorov and Barzdin (GZIP)

CS-2000-12
Title	Three-Dimensional Orthogonal Graph Drawing with Optimal Volume
Authors	T.C. Biedl, T. Thiele and D.R. Wood
Abstract	An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid which only possibly intersect at common endpoints. In this paper, we study three-dimensional orthogonal drawings and provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2) drawings where the surface of vertices is proportional to their degree, and (3) drawings without any such restrictions. Then we show that these lower bounds are asymptotically optimal, by providing constructions that match the lower bounds in all scenarios within an order of magnitude.
Date	January 2001
Comments	The paper will appear at Graph Drawing 2000, and has been submitted to Discrete and Computational Geometry.
Report	Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (PDF)			Compressed PostScript: Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (GZIP)

CS-2000-11
Title	Exploiting Functional Dependence in Query Optimization
Authors	G.N. Paulley
Abstract	Functional dependency analysis can be applied to various problems in query optimization: selectivity estimation, estimation of (intermediate) result sizes, order optimization (in particular sort avoidance), cost estimation, and various problems in the area of semantic query optimization. Dependency analysis in an ANSI SQL relational model, however, is made complex due to the existence of null values, three-valued logic, outer joins, and duplicate rows. In this thesis we define the notions of strict and lax functional dependencies, strict and lax equivalence constraints, and null constraints, which capture both a large set of the constraints implied by ANSI SQL query expressions, including outer joins, and a useful set of declarative constraints for ANSI SQL base tables, including unique, table, and referential integrity constraints. We develop and prove a sound set of inference axioms for this set of combined constraints, and formalize the set of constraints that hold in the result of each SQL algebraic operator. We define an extended functional dependency graph model (FD-graph) to represent these constraints, and present and prove correct a detailed polynomial-time algorithm to maintain this FD-graph for each algebraic operator. We illustrate the utility of this analysis with examples and additional theoretical results from two problem domains in query optimization: query rewrite optimizations that exploit uniqueness properties, and order optimization that exploits both functional dependencies and attribute equivalence. We show that the theory behind these two applications of dependency analysis is not only useful in relational database systems, but in non-relational database environments as well.
Date	May 2000
Comments	This PhD thesis defines the notions of strict and lax functional dependencies, strict and lax equivalence constraints, and null constraints in an ANSI SQL context, The thesis develops and proves a sound set of inference axioms for this set of combined constraints, and formalizes the set of constraints that hold in the result of each SQL algebraic operator. Two applications of these derived constraints are explored: query rewrite optimization and order optimization.
Report	Exploiting Functional Dependence in Query Optimization (PDF)			Compressed PostScript: Exploiting Functional Dependence in Query Optimization (PS.Z)

CS-2000-10
Title	Implementation of Some Triangular Data Fitting Schemes Using Averaging To Get Continuity
Authors	S. Mann
Abstract	In this paper, I describe the implementation details of some functional, triangular data fitting schemes. The schemes in question use derivative information to find initial settings of control points, giving a $C^0$, piecewise polynomial surface with a high degree of polynomial precision. The interior control points are then modified to increase the continuity between patches without decreasing the polynomial precision. In implementing these schemes, I had to address several issues, including basis conversion for bivariate functions, finding the weights of control points used to compute derivatives, and the construction of data sets for testing. In addition, I developed and tested a new scheme that uses fewer derivatives than the other schemes discussed in this paper.
Date	April 2000
Comments
Report	Implementation of Some Triangular Data Fitting Schemes Using Averaging To Get Continuity (PDF)			Compressed PostScript: Implementation of Some Triangular Data Fitting Schemes Using Averaging To Get Continuity (GZIP)

CS-2000-09
Title	Online Scheduling Revisited
Authors	R. Fleischer and M. Wahn
Abstract	We present a new online algorithm MR for non-preemptive scheduling of jobs with known processing times on m identical machines which beats the best previous algorithm for m>=64. For m approaching infinity its competitive ratio approaches 1+\sqrt{1+\ln 2\over 2}<1.9201.
Date	March 2000
Report	Online Scheduling Revisited (PDF)			Compressed PostScript: Online Scheduling Revisited (PS.Z)

CS-2000-08
Title	Balanced k-Colorings
Authors	T.C. Biedl, E. Cenek, T.M. Chan, E.D. Demaine, M.L.Demaine, R. Fleischer and M.-W. Wang
Abstract	While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k>=2, a set of vertices to minimize imbalance among a family of subsets of vertices. The imbalance is the maximum, over all subsets in the family, of the largest difference between the size of any two color classes in that subset. The discrepancy is the minimum possible imbalance. We show that the discrepancy is always at most 4d-3, where d (the ``dimension'') is the maximum number of subsets containing a common vertex. For 2-colorings, the bound on the discrepancy is at most max{2d-3,2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.
Date	March 2000
Report	Balanced k-Colorings (PDF)			Compressed PostScript: Balanced k-Colorings (PS.Z)

CS-2000-07
Title	Simplifying flow networks
Authors	Therese Biedl, Brona Brejova, Tomas Vinar
Abstract	Maximum flow problems appear in many practical applications. In this paper, we study how to simplify a given directed flow network by finding edges that can be removed without changing the value of the maximum flow. We give a number of approaches which are increasingly more complex and more time-consuming, but in exchange they remove more and more edges from the network.
Date	February 2000
Comments	Will be submitted to MFSC 2000
Report	Simplifying flow networks (PDF)			Compressed PostScript: Simplifying flow networks (PS.Z)

CS-2000-06
Title	How to Roll a Join: Asynchronous Incremental View Maintenance
Authors	K.M. Salem, K. Beyer, B. Lindsay and R. Cochrane
Date	February 28, 2000
Report	Report not in system

CS-2000-05
Title	Efficient Query Result Retrieval over the Web
Authors	E.P.F. Chan and K. Ueda
Date	February 2000
Report	Edward P.F. Chan's website

CS-2000-04
Title	Polygons needing many flipturns
Authors	T.C. Biedl
Abstract	A flipturn on a polygon consists of reversing the order of segments inside a pocket of the polygon, without changing lengths or slopes. Any n-link polygon can be convexified by performing at most (n-1)! flipturns. A very recent paper showed that in fact it is convex after at most n(n-1)/2 flipturns. We give here a lower bound by constructing a polygon such that if pockets are chosen in a bad way, at least (n-2)^2/4 flipturns are needed to convexify the polygon.
Date	January 2000
Comments	This paper will probably be submitted to CCCG 2000.
Report	Polygons needing many flipturns (PDF)			Compressed PostScript: Polygons needing many flipturns (GZIP)

CS-2000-03
Title	On the q-analogue of Zeilberger's algorithm to rational functions
Authors	H.Q. Le
Abstract	We consider the applicability (or terminating condition) of the q-analogue of Zeilberger's algorithm and give the complete solution to this problem for the case where the original q-hypergeometric term F(q^n,q^k) is a rational function.
Date	January 2000 (Revised, September 17, 2001)
Report	On the q-analogue of Zeilberger's algorithm to rational functions (PDF)			Compressed PostScript:On the q-analogue of Zeilberger's algorithm to rational functions (PS.Z)

CS-2000-02
Authors	E. Demaine
Date	Number issued, Jan.18/00
Report	Report not in system

CS-2000-01
Title	Continuity Adjustments to Triangular Bezier Patches That Retain Polynomial Precision
Authors	S. Mann
Abstract	In this paper, I discuss a method for increasing the continuity between two polynomial patches by adjusting their control points. The method described in this paper leaves the control points unchanged if the patches already meet with the desired level of continuity. Next I give two $C^0$ degree $n$ polynomial interpolation schemes that reproduce degree $n$ polynomials, and show how to apply my continuity increasing scheme to these interpolants without decreasing their polynomial precision. The second of these interpolants is interesting in its own right, as it requires less data than other methods. Finally, I apply my continuity method to Clough-Tocher methods, and create split domain schemes with top-level polynomial precision.
Date	January 2000
Report	Continuity Adjustments to Triangular Bezier Patches That Retain Polynomial Precision (PDF)			Compressed PostScript: Continuity Adjustments to Triangular Bezier Patches That Retain Polynomial Precision (GZIP)