Algorithms in combinatorial geometry
algorithms in computational geometryarrangements of hyperplanes in Euclidean spacescombinatorial geometryRadon theoremsearching Helly theoremsortingtime-complexityVoronoi diagrams
Exact enumeration problems, generating functions (05A15) Other designs, configurations (05B30) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02) Helly-type theorems and geometric transversal theory (52A35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
This monograph is devoted to computational geometry, a very active area of modern research that emerged in the early seventies and developed in strong connection with the older field of combinatorial geometry. The author's intention was ``to demonstrate that computational and combinatorial investigations in geometry are doomed to profit from each other. In the choice of topics, he was guided by the attempt ``to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure; accordung to this, he expresses his belief ``that arrangements of hyperplanes are at the very heart of computational geometry.... The book consists of three parts: I. Combinatorial geometry; II. Fundamental geometric algorithms; III. Geometric and algorithmic applications. Part I is a self-contained introduction to the combinatorial geometry of arrangements of hyperplanes in Euclidean spaces. It starts in chapter I with a presentation of the basic facts, including some enumeration formulas, a definition of combinatorial equivalence (which depends on the choice of a distinguished direction in the ambient space), a discussion of the duality between arrangements and configurations of points and some related structures. This is followed in chapter 2 by detailed study of circular sequences of permutations, which serve as a tool for encoding two-dimensional arrangements in the plane. Chapter 3 deals with the relationship between the number of semispaces of configurations with fixed cardinality and the number of faces of levels in arrangements of hyperplanes. Asymptotic lower and upper bounds are established on these numbers, mainly in the two-dimensional case. Chapter 4 contains a treatment of some problems concerning dissections of point sets. Included are proofs of Radon's and Helly's theorems and of a discrete version of the ham-sandwich theorem; various methods are developed, which provide results on balanced dissections of two- and three-dimensional point sets. An analysis of the cardinality of zones in arrangements is performed in chapter 5; tight bounds in the plane and asymptotic tight bounds in higher dimensions are derived. Chapter 6 approaches the investigation of the complexity of collections of cells chosen from an arrangement. Euler's formula and the Dehn-Sommerville relations for polytopes are obtained and used to derive an asymptotic version of the Upper Bound Theorem and various other results concerning upper and lower bounds for collections of cells. Part II of the book is devoted to the presentation of some fundamental geometric algorithms. One of the most important problems, that of constructing an arrangement of hyperplanes, is treated in chapter 7. A detailed description is given of an algorithm which operates incrementally (addition of one hyperplane at a time). The analysis of the time-complexity of this algorithm provides an upper bound for the number of combinatorially non-equivalent arrangements of n hyperplanes in \(E^ d\). Chapter 8 covers the problem of constructing the convex hull of a finite set of points in \(E^ d\). Two different approaches are described for sets of points in the plane: the beneath-beyond method (which is then generalized to all dimensions), and the divide-and-conquer paradigm (which is extended to dimension 3). Another method is presented in chapter 9, which applies to the construction of more complicated structures in arrangements (skeletons). The algorithm is outlined first for the case of simple arrangements; then, by using the technique of ``simulation of simplicity, it is extended to arbitrary arrangements. Both static and dynamic data structures are described and used. Chapter 10 contains a discussion of linear programming, with applications to other geometric problems. The algorithmic method used is prune-and- search, which is applied first to the 2-dimensional case, then to higher dimensions. Another fundamental geometric problem, that of locating a specific point in a given planar subdivision, is treated in chapter 11. An efficient solution (later improved to an optimal one) is obtained, first for monotone subdivisions, then for general subdivisions by using a refinement procedure. Part III of the book presents some applications, both algorithmic and combinatorial, of the results from the other two parts. Several problems where the transformation from configurations to arrangements reduces the difficulties encountered are discussed in chapter 12. A representative sample of six problems is presented: the computation of largest convex sets in the plane, the visibility graph for line segments, the determination of minimum measure simplices, two generalizations of sorting to higher dimensions, and a vector-sum maximization problem. Chapter 13 contains a detailed discussion of Voronoi diagrams (classical, higher-order, and with weighted sites), and of many of their applications. A few other applications of earlier results to separation and intersection problems in Euclidean spaces are derived in chapter 14. The final chapter 15 reviews and discusses some of the ``design paradigms from the text. Each of these methods (divide-and-conquer, incremental construction, and prune-and-search) is applied to an appropriate variant of a generic transversal problem defined in the plane (stabbing line segments). Static and dynamic solutions to related search problems are derived. Each chapter concludes with a collection of exercises and problems which provide results that extend the material presented in the text; some of these are in fact open research problems. Each of these collections is followed by a set of bibliographic notes. There is some overlap with other texts on computational geometry, such as the book by \textit{F. P. Preparata} and \textit{M. I. Shamos} [Computational geometry. An introduction. (1985; Zbl 0575.68059)] and Chapter VIII in \textit{K. Mehlhorn}'s monograph [Data structures and algorithms 3: Multi- dimensional searching and computational geometry. (1984; Zbl 0556.68003)], but the author offers here alternative approaches, with different methods and proofs. The book covers a lot of advanced material and leads the reader to very recent results and current research. It is certainly a valuable contribution towards the development and systematization of the area of computational geometry.
- Depth of segments and circles through points enclosing many points: A note
- A fast algorithm for the alpha-connected two-center decision problem
- On regular vertices of the union of planar convex objects
- A practical approximation algorithm for the LMS line estimator
- Point set stratification and Delaunay depth
- Dynamic ham-sandwich cuts in the plane
- The analysis and the representation of balanced complex polytopes in 2D
- A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation
- New results on lower bounds for the number of \((\leq k)\)-facets
- Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
- The power of geometric duality
- -nets and simplex range queries
- Edge-skeletons in arrangements with applications
- Minimum polygonal separation
- The complexity of cutting complexes
- An algorithmic approach to some problems in terrain navigation
- Topologically sweeping an arrangement
- Submodularity and the traveling salesman problem
- Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm
- Mathematical snapshots from the computational geometry landscape
- Compaction and separation algorithms for non-convex polygons and their applications
- Parallel computation of distance transforms
- Bounding the number of k-faces in arrangements of hyperplanes
- The complexity of point configurations
- Cutting hyperplane arrangements
- Euclidean minimum spanning trees and bichromatic closest pairs
- Small-dimensional linear programming and convex hulls made easy
- Points and triangles in the plane and halving planes in space
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Bisections and ham-sandwich cuts of convex polygons and polyhedra
- A role of lower semicontinuous functions in the combinatorial complexity of geometric problems
- On \(k\)-sets in arrangements of curves and surfaces
- A basis enumeration algorithm for linear systems with geometric applications
- Improved complexity bounds for location problems on the real line
- Randomized optimal algorithm for slope selection
- Satisfying general proximity/similarity queries with metric trees
- On disjoint concave chains in arrangements of (pseudo) lines
- An upper bound on the number of planar K-sets
- Almost tight bounds for -nets
- Tiling polygons with parallelograms
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Finding minimum area \(k\)-gons
- How to find Steiner minimal trees in Euclidean \(d\)-space
- Optimal parallel algorithms for point-set and polygon problems
- Counting facets and incidences
- A new representation and algorithm for constructing convex hulls in higher dimensional spaces
- Applications of random sampling to on-line algorithms in computational geometry
- Finding stabbing lines in 3-space
- Counting and cutting cycles of lines and rods in space
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- Delaunay triangulations in three dimensions with finite precision arithmetic
- The convergence rate of the sandwich algorithm for approximating convex functions
- Reporting points in halfspaces
- Intersection queries in sets of disks
- Fast algorithms for greedy triangulation
- Optimal time bounds for some proximity problems in the plane
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Transitions in geometric minimum spanning trees
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Efficient partition trees
- Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
- Upper envelope onion peeling
- Minimizing the sum of diameters efficiently
- The colored Tverberg's problem and complexes of injective functions
- On computing the exact value of dispersion of a sequence
- Hamiltonian triangulations and circumscribing polygons of disjoint line segments
- Convexity preserving interpolation and Powell-Sabin elements
- Geometric medians
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Parallel methods for visibility and shortest-path problems in simple polygons
- Axioms and hulls
- Stacks, queues, and deques with order-statistic operations
- The slab dividing approach to solve the Euclidean \(P\)-center problem
- The upper envelope of Voronoi surfaces and its applications
- Interval probability propagation
- Degree constrained tree embedding into points in the plane
- Cutting hyperplanes for divide-and-conquer
- On the zone of a surface in a hyperplane arrangement
- On the randomized construction of the Delaunay tree
- An efficient algorithm for finding the CSG representation of a simple polygon
- On arrangements of Jordan arcs with three intersections per pair
- Implicitly representing arrangements of lines or segments
- A computational basis for higher-dimensional computational geometry and applications
- On some geometric selection and optimization problems via sorted matrices
- Isolating points by lines in the plane
- Finding minimum area simple pentagons
- The catline for deep regression
- A nearly parallel algorithm for the Voronoi diagram of a convex polygon
- Detecting geometric infeasibility
- The widest k-dense corridor problems
- Guarding galleries where no point sees a small area.
- Noise-tolerant parallel learning of geometric concepts
- Stabbing information of a simple polygon
- Solving restricted line location problems via a dual interpretation
- Halfspace depth and regression depth characterize the empirical distribution
- An approximate algorithm for computing multidimensional convex hulls
- Bipartite embeddings of trees in the plane
- A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works
This page was built for publication: Algorithms in combinatorial geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3772828)