Related Research Articles
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.
In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.
In discrete geometry, a -set of a finite point set in the Euclidean plane is a subset of elements of that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a -set of a finite point set is a subset of elements that can be separated from the remaining points by a hyperplane. In particular, when , the line or hyperplane that separates a -set from the rest of is a halving line or halving plane.
Micha Sharir is an Israeli mathematician and computer scientist. He is a professor at Tel Aviv University, notable for his contributions to computational geometry and combinatorial geometry, having authored hundreds of papers.
In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.
In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are allowed. Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations. Following Atallah (1985) these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.
Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.
György Elekes was a Hungarian mathematician and computer scientist who specialized in Combinatorial geometry and Combinatorial set theory. He may be best known for his work in the field that would eventually be called Additive Combinatorics. Particularly notable was his "ingenious" application of the Szemerédi–Trotter theorem to improve the best known lower bound for the sum-product problem. He also proved that any polynomial-time algorithm approximating the volume of convex bodies must have a multiplicative error, and the error grows exponentially on the dimension. With Micha Sharir he set up a framework which eventually led Guth and Katz to the solution of the Erdős distinct distances problem.
In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.
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.
A kinetic triangulation data structure is a kinetic data structure that maintains a triangulation of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve motion planning, such as video games, virtual reality, dynamic simulations and robotics.
Richard M. Pollack was an American geometer who spent most of his career at the Courant Institute of Mathematical Sciences at New York University, where he was Professor Emeritus until his death.
In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.
In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.
Daniel Halperin is an Israeli computer scientist specializing in computational geometry and robot motion planning. He is a professor of computer science at Tel Aviv University.
Sariel Har-Peled is an Israeli–American computer scientist known for his research in computational geometry. He is a Donald Biggar Willett Professor in Engineering at the University of Illinois at Urbana–Champaign.
Davenport–Schinzel Sequences and Their Geometric Applications is a book in discrete geometry. It was written by Micha Sharir and Pankaj K. Agarwal, and published by Cambridge University Press in 1995, with a paperback reprint in 2010.
In geometry, the zone theorem is a result that establishes the complexity of the zone of a line in an arrangement of lines.
References
- ↑ "Pankaj Agarwal: New Chair of the Computer Science Department", Duke Computer Science Enews, September 2004, archived from the original on 2016-03-04, retrieved 2011-01-16.
- ↑ Pankaj Kumar Agarwal at the Mathematics Genealogy Project.
- ↑ Review of Intersection and Decomposition Algorithms for Planar Arrangements by Franz Aurenhammer, 1992, MR 1118839.
- ↑ Review of Davenport–Schinzel Sequences and their Geometric Applications by Igor Rivin, 1996, MR 1329734.
- ↑ Review of Combinatorial Geometry by Martin Henk, 1996, MR 1354145.
- ↑ ACM Fellows Award: Pankaj K. Agarwal, ACM, retrieved 2011-01-16.
- 1 2 "Seats of Learning", Duke University Alumni Magazine, 28, May–June 2000.
