Examples Illustrating some Aspects of the Weak Deligne-Simpson Problem

Research partially supported by INTAS grant 97-1644

Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons

We consider the problems of finding two optimal triangulations of a convex polygon: MaxMin area and MinMax area. These are the triangulations that maximize the area of the smallest area triangle in a triangulation, and respectively minimize the area of the largest area triangle in a triangulation, over all possible triangulations. The problem was originally solved by Klincsek by dynamic programming in cubic time [2]. Later, Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time [1]. In this paper we describe new geometric findings on the structure of MaxMin and MinMax Area triangulations of convex polygons in two dimensions and their algorithmic implications. We improve the algorithm’s running time to quadratic for large classes of convex polygons. We also present experimental results on MaxMin area triangulation.

A Super-Dimension Approach in ROLAP Environments

Often the designer of ROLAP applications follows up with the question “can I create a little joiner table with just the two dimension keys and then connect that table to the fact table?” In a classic dimensional model there are two options - (a) both dimensions are modeled independently or (b) two dimensions are combined into a super-dimension with a single key. The second approach is not widely used in ROLAP environments but it is an important sparsity handling method in MOLAP systems. In ROLAP this design technique can also bring storage and performance benefits, although the model becomes more complicated. The dependency between dimensions is a key factor that the designers have to consider when choosing between the two options. In this paper we present the results of our storage and performance experiments over a real life data cubes in reference to these design approaches. Some conclusions are drawn.

Dispersive Estimates of Solutions to the Wave Equation with a Potential in Dimensions Two and Three

2000 Mathematics Subject Classification: 35L15, 35B40, 47F05.