Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation.
In geometry, an arrangement of lines is the subdivision of the Euclidean plane formed by a finite set of lines. An arrangement consists of bounded and unbounded convex polygons, the cells of the arrangement, line segments and rays, the edges of the arrangement, and points where two or more lines cross, the vertices of the arrangement. When considered in the projective plane rather than in the Euclidean plane, every two lines cross, and an arrangement is the projective dual to a finite set of points. Arrangements of lines have also been considered in the hyperbolic plane, and generalized to pseudolines, curves that have similar topological properties to lines. The initial study of arrangements has been attributed to an 1826 paper by Jakob Steiner.
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.
Zvi Galil is an Israeli-American computer scientist and mathematician. He has served as the dean of the Columbia University School of Engineering and as president of Tel Aviv University from 2007 through 2009. From 2010 to 2019, he was the dean of the Georgia Institute of Technology College of Computing.
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from p to q whenever q is a nearest neighbor of p, a point whose distance from p is minimum among all the given points other than p itself.
Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.
Frances Foong Chu Yao is a Taiwanese-American mathematician and theoretical computer scientist. She is currently a Chair Professor at the Institute for Interdisciplinary Information Sciences (IIIS) of Tsinghua University. She was Chair Professor and Head of the Department of computer science at the City University of Hong Kong, where she is now an honorary professor.
In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.
Roberto Tamassia is an American Italian computer scientist, the Plastech Professor of Computer Science at Brown University, and served as the chair of the Brown Computer Science department from 2007 to 2014. His research specialty is in the design and analysis of algorithms for graph drawing, computational geometry, and computer security; he is also the author of several textbooks.
Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Distinguished Professor and Department Chair of Applied Mathematics and Statistics and Research Professor of Computer Science at Stony Brook University.
Emmerich (Emo) Welzl is a computer scientist known for his research in computational geometry. He is a professor in the Institute for Theoretical Computer Science at ETH Zurich in Switzerland.
Subhash Suri is an Indian-American computer scientist, a professor at the University of California, Santa Barbara. He is known for his research in computational geometry, computer networks, and algorithmic game theory.
John E. Hershberger is an American computer scientist and software professional, a principal engineer at Mentor Graphics Corporation since 1993. He is known for his research in computational geometry and algorithm engineering.
In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.
Giuseppe Francesco (Pino) Italiano is an Italian computer scientist. He is a professor of computer science at LUISS University in Rome. He is known for his work in graph algorithms, data structures and algorithm engineering.
In computational geometry, a greedy geometric spanner is an undirected graph whose distances approximate the Euclidean distances among a finite set of points in a Euclidean space. The vertices of the graph represent these points. The edges of the spanner are selected by a greedy algorithm that includes an edge whenever its two endpoints are not connected by a short path of shorter edges. The greedy spanner was first described in the PhD thesis of Gautam Das and conference paper and subsequent journal paper by Ingo Althöfer et al. These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.
