Efficient algorithms for sequencing, counting, manipulating and visualizating discrete structures

点击翻译按钮获取中文摘要

The purpose of this research is to investigate essential algorithmic and mathematical properties of certain fundamental discrete structures, including Venn/Euler diagrams, Gray codes, nested recurrence relations, and polynomials over finite fields. Of these structures, Venn/Euler diagrams will be most familiar to the general public. Formally, a Venn diagram consists of n simple closed curves drawn in the plane with the property that each of the 2^n intersections of the interiors or exteriors of the curves is non-empty and connected. If regions are allowed to be empty, then it is an Euler diagram. There is a demand for software that will render "Venn" diagrams of populations in such a way that the area of each region is in proportion to the size of the underlying population. Basic questions about when this is possible, and if possible, how to best draw the diagram from the users point of view, are still unresolved, although some progress has been made. One goal of this research is to resolve these questions.