With Scott Douglass, Department of Civil Engineering. Funding is being sought from the Coastal Transportation Engineering Research and Education Center.
eDune software.
Group Theoretical Research Software Tool
Building a research software tool for topology and combinatorial group theory, with applications to knot theory. With Dan Silver, and Susan Williams of the Department of Mathematics and Statistics, and Natalie Shirley.
Fax Image Improvement
The goal of this work with Andreas Skaret is to find an algorithm to process a faxed binary image of a text document, to produce a gray-scale image that is more readable and aesthetically pleasing. Our approach will be intermediate between content-oblivious image processing, and content-constraining OCR.
Trapezoidalization of Simple polygons
A fast, practical algorithm has been developed for the trapezoidalization of simple polygons. This is a classical problem in computational geometry, closely related to polygon triangulation. The current implementation is ~40 times faster for practically occurring polygons, and 15 times faster for random polygons, than Seidel's algorithm, the fastest (previously) known algorithm.
Variations of the algorithm for disjoint (multipath) polygons have been developed using both even parity and non-zero winding number rules.
Lavanya Subramaniam is currently working on implementing an algorithm for resolving complex polygons (having crossing edges) into simple fragments (with both even parity and non-zero winding number rules.) This will enable the trapezoidalization algorithm to be applied to complex polygons.
This work was funded for 2½ years by QMS, Inc.
Fast Rendering of Thick Polylines
Given a path and a thickness, a fast algorithm for the polygonal representation of a solid polyline is being investigated. Some initial work on this project has been done by Ken Onuka, and currently being research by Subramani Swaminadhan.
Rendering of Bézier Curves
Bézier curves are normally flattened (approximated by polylines) by such techniques as recursive subdivision or forward differencing. A new fast method for stopping recursion at an appropriate level has been developed (with a concomitant reduction of the required number of line segments.) ( Paper )
Methods have been developed with Athar Ahmad for reducing the segment count even further. (Paper / Foils)
Initially with Elena Galaktionova and now with Sri Venkat Rao Racherla—the rendering of thick Bézier curves by offset curve approximation, and reduction to minimal vertex polygons has been investigated. (Paper)
Graph Isomorphism
With Geof Goldbogen—an O(V²) algorithm for the determination of graph isomorphism using an invariant called the greatest characteristic vector (GCV)
Learning Styles
With Dr. William Owen