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