I am interested in Computational Geometry, Algorithms and Data Structures, and Discrete Mathematics. I enjoy investigating both theoretical issues and applied problems. I am especially interested in biological and medical applications. My recent research focusses on Shape Matching, Discrete Geometry, Graph Drawing, and medical and biological applications.

• In computational geometry we deal with geometric algorithms. So, for example, imagine a few pins on a pinboard, and now hold a rubber band around them, and let the rubber band go. It will form a polygon around the pins, which is called the convex hull of the pins. How do you compute it?

• I am especially interested in shape matching. Given two shapes (say, two polygons in the plane), how similar are they? Can you translate, or maybe also rotate, one of them to be close to the other? And what does it mean at all for two shapes to be close to one another? There are many applications of shape matching, for example in robotics, computer graphics, image processing, and more. I've worked on shape matching in higher dimensions, shape matching in 2D electrophoresis gels (see more below), and on finding a GPS curve in a roadmap (see the video).

• In graph drawing we are given a graph and we wish to visualize it. This means, we wish to draw it (in the plane, but possibly also in 3D) in a nice way. Of course, nice is not well defined, and in fact nice depends on the application or on the user. Often we want to draw the graph with as few edge crossings as possible (planar graphs we can even draw without edge crossings!), and often we wish to draw the edges as straight-line segments. Also, the space into which we draw the graph may be limited. Or, we might want to compare two graphs, so we need to draw them together such that we can compare them easily. I worked on drawing "fat graphs", see the video ([avi], [gzipped avi]).

• There are many geometric problems that arise in biology or medicine, especially image analysis problems. In proteomics for example, which is the field of protein analysis, protein samples are separated using a technology called 2D gel electrophoresis. This produces images, in which every dark spot corresponds to one protein. Eventually one would like to compare several images (which is basically a point matching problem; it is similar to considering the starry sky and comparing different star constellations), which is called gel matching. But first one needs to segment the image into the spot areas (spot detection). Both tasks are not straight-forward, and still need a lot of human help nowadays, which is slow and costly. And pharmaceutical companies are very much interested in automizing these processes as much as possible. I've participated in designing a gel matching system called CAROL, see also the poster. Right now CAROL is integrated into the 2D gel analysis software PDQuest by BioRad.
  

Possible topics for independent studies, masters research, or PhD research
The following is a non-comprehensive list of possible research topics. If you are a UTSA student and are interested in working with me on any of these topics, or are interested to learn more about my research interests, please contact me.

• Model design and fitting for spot detection in 2D electrophoresis gels
• Map-Matching and Routing Algorithms for Traffic Estimation and Prediction Systems
• Map construction from GPS curves
  How do you construct a hiking trail map if the trails are in a forest such that you cannot see much in an areal picture? Equip some hikers with GPS receivers, and send them out to hike on the trails. You end up having a set of GPS curves, and now wish to merge them into a single map of hiking trails. Unfortunately, the GPS signal is quite noisy and the affordable devices are not extremely precise. So, if you have a partial map already and just one GPS curve, a prerequisite is that you know how to find the curve in the map that is closest to the GPS curve. See the video, which shows one way how to do this using the Frechet distance as a distance measure between two curves.

  Open questions are:

  • Can we use other distance measures which are well-suited for curves? For example, the weak Frechet distance, dynamic time warping, or a variant of the turning function?
  • Partial matching. Can you find a curve in the map which partially matches the given GPS curve? Which minimal length should it have?
  • Given several curves which are known to describe the same hiking trail. How do you merge them together? What's their "average"? Currently there is only a 2-approximation known.
  
  
• 2D Frechet distance
  The Frechet distance is a well-suited distance measure for curves, since, compared to the Hausdorff distance, it takes the continuity of the curves into account. See the beginning of the video for the definition. One can also define the Frechet distance for two two-dimensional (say, triangulated) surfaces. But unfortunately it is NP-hard to compute this 2D Frechet distance.

  Open questions are:

  • Can one compute the 2D Frechet distance at all? Even in exponential time? Can one prove that the problem is in NP?
  • Can one approximate the 2D Frechet distance (with an approximation guarantee) in polynomial time?
  • Can one define a hybrid between Hausdorff and Frechet distance which is easier to compute or approximate?

• Geodesic distances for shapes
  There are several distances for shapes, such as the Hausdorff distance, or the Frechet distance for example. These distances are usually defined for shapes in a two-dimensional space, or a three-dimensional space, or even in higher dimensions. Either of these distances uses "as a subroutine" the Euclidean distance between two points.

  However, suppose you're given two curves on a terrain (so, there are several "mountains" between the curves). Then the distance between two points on the terrain is not the Euclidean "straight-line" distance, because you cannot walk right through the mountains. So, it makes sense to consider the geodesic distance between two points, which is the length of a shortest path between the points on the terrain.

  Open questions are:

  • How can we compute the geodesic Hausdorff distance of a set of points (this should be easy), and of a set of line segments?
  • How can we compute the geodesic Frechet distance of two curves?
  • For which underlying surfaces do our algorithms work -- convex polyhedra, terrains, ... ?

• Modelling Purkinje cells
  A Purkinje cell (see [1], [2], [3], [4], [5], [6], [7]) is an important neuron in the cerebellum. It basically forms a binary tree in 3D, where the branches can have three different thicknesses. [This is a collaboration with Jim Bower from UTSA and the UT Health Science Center]

  Open questions are:

  • Given 3D images of several different Purkinje cells. Can we learn the structure of the Purkinje cells? Can we define a statistical model of a Purkinje cell? What are the spatial distributions of the different branch thicknesses?
  • How can we simplify the model of a given Purkinje cell (group branches / subtrees together into simpler entities) such that it still has the same interaction behavior with other neurons? We would test the interaction behavior with the modelling software Genesis.

• Simultaneous embedding of graphs
  Suppose you're given a set of vertices, and two different graphs on these vertices: The red graph is a path, and the blue graph is a, say binary, tree. Can you position the vertices in the plane, such that both the red edges and the blue edges are straight line segments, and no two red edges cross, and no two blue edges cross?

  Since both graphs are planar, it is easy to embed each of them separately. But there is not much known about simultaneous graph embeddings like this. Why is this interesting at all? Many people wish to compare two graphs, for example, biologists compare phylogenetic trees. These are two trees on the same vertex set, so, the question would be: Can you embed two trees simultaneously with straight-line segments, such that each tree is embedded with non-crossing edges?

• Fitting prehistoric stone knives
  Prehistoric people produced stone knives by chopping the main piece for the knife off a core stone, and then refining this main piece by several smaller chops. Archaeologists are now interested in finding out which stone knives have been chopped from the same core stone (because this gives information about social behavior, like trading of stone knives). Currently, archaeologists assemble these stone knives manually. But from a computational point of view it is a surface matching problem, because the knife and the core stone share the common chopping surface. This surface is almost planar (however, it usually also contains a bulb-shape), which makes it hard to identify geometric features. So, one has to carefully detect the few geometric features that the chopping surfaces exhibits. Furthermore, the underlying stone of the stone knives often contains color patterns, which give additional clues for the matching.

  The tasks are to scan in stone knives (with a range scanner which captures geometric information and with a camera in order to capture the color information), extract geometric features and color features, and design algorithms to compare (and assemble) different stone knives.