UT Dallas Computer Science Researchers Make Two Important Discoveries in Computational Geometry
Dr. Benjamin Raichel, assistant professor of computer science, and his collaborators recently made two important discoveries in the area of computational geometry.
Computational geometry is a field of study devoted to the development of efficient algorithms for problems which can be stated in geometric terms. As data sets of all sizes are routinely and naturally described geometrically as points in space, the applications of computational geometry are far reaching. When studying problems relating to the three-dimensional physical world, computational geometry is inseparable from research areas such as graphics, scientific computing and modeling, and computer vision. Even when the data is not the result of some physical process, representing it geometrically can pay dividends due to powerful geometric tools which can be brought to bear on the given problem. Such is the case for machine learning and related areas of research, where it is standard to represent objects of study as high dimensional feature vectors, resulting in algorithms with numerous geometric insights at their core.
The first discovery, reported in the paper titled “Computing the Frechet Gap Distance”, co-authored with Ph.D. student Chenglin Fan, will appear in the 33rd Symposium on Computational Geometry (SoCG), to be held in Brisbane, Australia, July 4-7, 2017. The second paper titled “A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs,” co-authored with Dr. Amir Nayyeri of the Oregon State University, appeared in the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), held January 16-19, 2017, in Barcelona, Spain.
The SoCG paper concerns computing the Frechet gap distance. Given two curves (described as ordered sequences of points), the problem pertains to computing how similar these curves are. For example, given GPS data and a road network map, can the GPS data be aligned with the path in the map taken by the traveler? One of the most common curve distance measures is the Frechet distance, typically illustrated as follows: A man is placed at the start of one curve, a dog at the start of the other, and they are connected by a leash. The man and dog must walk to the ends of their curves, and each can vary their speed independently but cannot backtrack. The Frechet distance is then the minimum leash length needed over all possible walks. In the SoCG paper Fan and Raichel study a variant called the Frechet gap distance which, rather than minimizing the longest length of the leash, instead minimizes the difference between the longest and shortest lengths over the traversal. For this problem, they provide a polynomial time exact algorithm, and a much faster quadratic time approximation algorithm. This measure is of interest since in some ways it better captures our intuitive notion of what “similar curves” means, for example, it is invariant to translations of the curves.
The SODA paper concerns the problem of metric embeddings. Given a graph G (or alternatively a finite point set in a metric space), the goal is to embed it into a larger graph H. Specifically, each vertex in G must be mapped onto a vertex in H, such that the distance between any pair of vertices in G is close to the distance of the mapped pair in H. In other words we make an attempt to determine how much G “looks” like a part of H. This basic problem is of fundamental importance in computer science. For example, if it is known that G looks like some simpler graph, say, a tree, then we can design more efficient algorithms for problems involving G. This problem is also closely related to the famous graph isomorphism problem. It is provably a very hard problem and there isn’t always a good embedding. However, Nayyeri and Raichel showed that if the graph has “sufficient” structure and if there is a “nice” embedding, then one can find a good approximation to this embedding in polynomial time.
Dr. Raichel is an assistant professor of computer science at UT Dallas. He joined the department in the Fall semester of 2015. Dr. Raichel’s research focuses on algorithmic design and more specifically the combination of computational geometry with other subfields of algorithms and computer science. He has published papers in the ACM Symposium on the Theory of Computing (STOC), the IEEE Foundations of Computer Science (FOCS), and the ACM-SIAM Symposium on Discrete Algorithms (SODA), the top theoretical computer science conferences. Additionally, he has published numerous papers in the Symposium on Computational Geometry (SoCG), the leading conference in computational geometry. Before joining UT Dallas, Dr. Raichel was a Ph.D. student at the University of Illinois, Urbana-Champaign, under the supervision of his advisor, Professor Sariel Har-Peled. Dr. Raichel also holds an M.S. degree from the University of Illinois, Urbana-Champaign, and a B.S. degree with a double major in Mathematics and Physics.
As problems concerning data analysis are often either directly stated geometrically or can be recast in geometric terms, computational geometry is an area of study with far reaching applications throughout computer science. In the past, Dr. Raichel has worked on various fundamental topics in the field such as metric embeddings, convex hulls, Voronoi diagrams, nearest neighbor queries, clustering, curve similarity, computational topology, geometric optimization, and more. In particular, his research involves the application of tools such as randomization and approximation to these core topics in order to push the boundaries of the field. Dr. Raichel has also been involved in research relating to recent trends in the field, such as the study of uncertain and probabilistic data.
Many of the past achievements in computational geometry focused on low dimensional spaces where the tools are much richer and stronger results can be achieved. Naturally, as we live in a 3D world, the applications of such results are far reaching throughout the sciences. However, more recently there has been increasing demand for high dimensional data analysis, stemming from application areas such as machine learning. As a result, a recent focus of Dr. Raichel’s research concerns problems relating to high dimensional data analysis. In recent years Dr. Raichel has published in top conferences on the topic of metric embeddings, as well as on efficient and practical algorithms for extracting coresets to approximate the convex and conic hulls in high dimensions.
Dr. Raichel’s research in computational geometry is funded by the NSF CRII grant Breaking Barriers for Geometric Data.
ABOUT THE UT DALLAS COMPUTER SCIENCE DEPARTMENT
The UT Dallas Computer Science program is one of the largest Computer Science departments in the United States with over 2,100 bachelor’s-degree students, more than 1,000 MS master’s students, 150 PhD students, and 86 faculty members, as of Fall 2016. With The University of Texas at Dallas’ unique history of starting as a graduate institution first, the CS Department is built on a legacy of valuing innovative research and providing advanced training for software engineers and computer scientists.