The objective of this research is to help increase speed, quality, and productivity of shape handling in practice. Geometric shapes are at the core of a wide range of cutting-edge technological sectors including computer vision, computer aided design (CAD), robotics, bioinformatics, computational biology, medical imaging, geographical information systems (GIS), and drug design, in which a multitude of tasks for manipulating and handling geometric shapes have to be performed efficiently and reliably.
This research is based on two research tracks: (i) shape handling applications and (ii) shape handling theory. The investigator will continue to foster interdisciplinary communication, contribute more theoretical soundness to applied problems, and pursue a stronger theoretical foundation which can be the basis for a wider range of applications. Specifically, this research involves several applied projects including, but not limited to, computational proteomics, computational neuroscience, and spatiotemporal traffic databases. Semi-automatic algorithms will be combined with theoretical expertise in order to pave the road for high-throughput processing in areas with very noisy data. Theoretical projects include matching and distance measure problems for curves and surfaces, multi-curve matching, initiation of a general study of geodesic distance measures in which distances are measured using shortest paths on a surface, and shape simplification. Lower bounds will be investigated in order to gain better insight into the structure of the problems, and application-friendly algorithms such as output-sensitive algorithms and approximation algorithms will be devised in order to better cope with outliers and noisy inputs.
This project has provided several algorithmic advances for increasing speed, quality, and productivity of handling discrete geometric shapes. The work was carried out in several smaller sub-projects that covered a wide spectrum from theoretical foundations to various interdisciplinary applications of shape handling. This project has involved two PhD students, four Masters students, and ten undergraduate students, and it was conducted in collaboration with multiple partner institutions in five countries. All involved students gained valuable experience in conducting interdisciplinary research by participating in this project. The results of this project have been disseminated through participation in conferences and workshops and through publications in various peer-reviewed conferences and journals. Contributions to the theoretical foundations of geometric algorithms for shape handling have been made in the following areas: 1) Geodesic Frechet distance and shortest path structures This project initiated the study of geodesic Frechet distance. Here, the underlying metric to measure distance between two points takes the ambient space and obstacles into account; examples are the length of a shortest obstacle-avoiding path or the minimum number of straight-line links necessary to connect the two points. Novel contributions include shortest path maps and Voronoi diagrams for the geodesic Frechet distance, as well as algorithms to efficiently compute the geodesic Frechet distance for curves in the plane and on convex polyhedra. 2) Similarity metrics for curves and surfaces This project has improved the state of the art in computer science for computing the Frechet distance for surfaces and curves. In the case of curves, a general class of curves was identified for which their Frechet distance can be approximated in near-linear time, which constitutes the first dramatic runtime improvement for computing the Frechet distance. For surfaces, the project has made significant contributions towards narrowing the complexity gap for computing the Frechet distance between surfaces: It has provided an algorithm with improved runtime for simple polygons as well as the first efficient approximation algorithm for the case of two folded polygons, and it has introduced the new notions of partial Frechet distance and of simple curve embeddings. The latter has provided important insights into the hardness of computing the Frechet distance between surfaces. Contributions to interdisciplinary applications of geometric shape handling have been made in the following areas: 3) Map-matching of GPS trajectory data Map-matching is the important task of processing a road network graph to find a path that corresponds to a given GPS trajectory. This project has employed the weak Frechet distance to provide the first map-matching algorithm that gives a quality guarantee for the matching and that runs fast on large data sets. It has produced valuable travel time data for motor vehicles, which is important for routing queries in personal navigation systems. This is a showcase application of a new algorithmic technique that has immediate impact in practice. Map-matching was also used to develop a simple and elegant map construction algorithm which has the potential to be employed in wide array of application areas to construct or update road networks from trajectory data. The project has also helped formalize the notion of a median trajectory for a set of trajectories, and provided algorithms to compute median trajectories, which is important in the GIS community for map construction and for clustering trajectories. Map-matching has also been applied to enable skeleton-based recognition of shapes in images, by map-matching a longest path of one shape skeleton into the skeleton of another shape. 4) Shape handling for biomedical applications This project has applied innovative algorithmic approaches to several biomedical areas. New shape models have been developed for teardrop spot detection in two-dimensional protein electrophoresis gels, and new noise models have been developed to improve protein quantification in tandem mass spectroscopy with isobaric labeling. The project has also provided the first algorithm to find a shortest path for a bevel-tip needle through a given sequence of target points; this has medical applications in brachytherapy and biopsy extraction, and it has the potential to allow doctors to reach more target areas with fewer needle punctures. Finally, the project has applied a variation of the directed Hausdorff distance to obtain a novel method for quantitative analysis of confocal images depicting protein trafficking behavior; this has led to the first quantitative results in this area.
