CS200022  

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) 
CS200021  

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) 
CS200020  

Title  The Verification of Hypermedia Design Composition  
Authors  Jing Dong, Paulo S. C. Alencar, Donald D. Cowan  
Abstract  Developing largescale 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 componentbased 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) 
CS200019  

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 timecomplexity when solving a threerow 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) 
CS200018  

Authors  A. An  
Report  No report 
CS200017  

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 3regular 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) 
CS200016  

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

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 
CS200015.mpg.gz

gzipped
MPEG
demonstrating
some
of
the
direct
manipulation
techniques CS200015.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) 
CS200014  

Title  SMASH: A NextGeneration API for Programmable Graphics Accelerators  
Authors  M. McCool  
Date  July 2000  
Report  SMASH: A NextGeneration API for Programmable Graphics Accelerators (PDF) 
CS200013  

Title  Crosscoloring: 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 edgecoloring in a bipartite graph. Using this result we reduce significantly the time complexity and the volume bounds of algorithms for threedimensional 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  Crosscoloring: improving the technique by Kolmogorov and Barzdin (PDF) 
Compressed
PostScript: Crosscoloring: improving the technique by Kolmogorov and Barzdin (GZIP) 
CS200012  

Title  ThreeDimensional 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 axisaligned boxes, and edges represented by paths in the grid which only possibly intersect at common endpoints. In this paper, we study threedimensional 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  ThreeDimensional Orthogonal Graph Drawing with Optimal Volume (PDF) 
Compressed
PostScript: ThreeDimensional Orthogonal Graph Drawing with Optimal Volume (GZIP) 
CS200011  

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, threevalued 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 (FDgraph) to represent these constraints, and present and prove correct a detailed polynomialtime algorithm to maintain this FDgraph 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 nonrelational 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) 
CS200010  

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) 
CS200009  

Title  Online Scheduling Revisited  
Authors  R. Fleischer and M. Wahn  
Abstract  We present a new online algorithm MR for nonpreemptive 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) 
CS200008  

Title  Balanced kColorings  
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 2colorings, we explore the problem of kcoloring, 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 4d3, where d (the ``dimension'') is the maximum number of subsets containing a common vertex. For 2colorings, the bound on the discrepancy is at most max{2d3,2}. Finally, we prove that several restricted versions of computing the discrepancy are NPcomplete.  
Date  March 2000  
Report  Balanced kColorings (PDF) 
Compressed
PostScript: Balanced kColorings (PS.Z) 
CS200007  

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 timeconsuming, 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) 
CS200006  

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 
CS200005  

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 
CS200004  

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 nlink polygon can be convexified by performing at most (n1)! flipturns. A very recent paper showed that in fact it is convex after at most n(n1)/2 flipturns. We give here a lower bound by constructing a polygon such that if pockets are chosen in a bad way, at least (n2)^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) 
CS200003  

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

Authors  E. Demaine  
Date  Number issued, Jan.18/00  
Report  Report not in system 
CS200001  

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 CloughTocher methods, and create split domain schemes with toplevel 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) 