Computational geometry. Algorithms and applications
This remarkable textbook offers a ``hands-on introduction to computational geometry. It is intended as a textbook, with a discussion of various topics related to the implementation of such algorithms: the data representation used in most of the geometric structures is the doubly-connected edge-list (Chapter 2); legible pseudo-code is given for all the algorithms; and a short motivation introduces each chapter to give some ideas on how the algorithm could be used. I found the latter a good and useful innovation (even though I would have picked different examples for some chapters). It also gives the reader a sense of in what domains computational geometry could be applied: the motivations stem among other fields from geographic information systems (GIS), manufacturing, computer graphics, and robotics. This makes it an ideal reference to use it for introductory lectures on computational geometry. Since the goals and methods of this textbook are similar to that by \textit{J. O'Rourke} [Computational geometry in C, Cambridge Univ. Press (1994; Zbl 0816.68124)], many comments made for that book also apply to this one. As for the contents, one finds convex hulls (Chapters 1 and 11) and linear programming (Chapter 4); line segments intersections and related problems about planar maps (Chapter 2) and point location (Chapter 6); arrangements of lines (Chapter 8); triangulations (Chapters 3 and 9) and Voronoi diagrams (Chapter 7); geometric data structures for searching (Chapters 5, 10, 12, 14, and 16) and visibility (Chapter 15). The book treats quite well all the aspects of two- and three-dimensional geometry. It does not give the most theoretically efficient solution to some problems, but always one simple and reasonably efficient solution can be derived from the material. One should not expect in the text a treatment of four- and higher-dimensional structures (except for orthogonal range searching and linear programming). Nevertheless, the notes give some pointers in this direction. The reader looking for such information should consult the more advanced books by \textit{H. Edelsbrunner} [Algorithms in combinatorial geometry (1987; Zbl 0634.52001)] or \textit{J.-D. Boissonnat} and \textit{M. Yvinec} [Géométrie algorithmique, Ediscience, Paris (1995)].
- Low complexity algorithms for optimal consumer push-pull partial covering in the plane
- Constrained Minkowski sums: A geometric framework for solving interval problems in computational biology efficiently
- Homogeneous 2-hop broadcast in 2D
- Searching for equilibrium positions in a game of political competition with restrictions
- Facility location problems in the plane based on reverse nearest neighbor queries
- A computational basis for higher-dimensional computational geometry and applications
- Special issue on Applied computational geometry
- Optimal placement of convex polygons to maximize point containment
- Fast tree-based redistancing for level set computations
- Tree methods for moving interfaces
- Geometric algorithms and combinatorial optimization.
- Indexing moving points
- First order Gaussian graphs for efficient structure classification
- Approximation of diffusion operators with discontinuous tensor coefficients on distorted meshes.
- On simplifying dot maps.
- Speeding up the incremental construction of the union of geometric objects in practice.
- Median problem in some plane triangulations and quadrangulations.
- A finite volume method for the approximation of diffusion operators on distorted meshes
- A fast modular semi-Lagrangian method for moving interfaces
- Triangulations in CGAL
- Delaunay refinement algorithms for triangular mesh generation
- Higher order Delaunay triangulations
- Multiple covers with balls. I: Inclusion-exclusion
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- Near-linear time approximation schemes for geometric maximum coverage
- Average adjacencies for tetrahedral skeleton-regular partitions
- Optimizing a constrained convex polygonal annulus
- Local polyhedra and geometric graphs
- Recent progress in exact geometric computation
- The least-squares meshfree method for the steady incompressible viscous flow
- On the flatness of Minkowski sums
- Walking around fat obstacles.
- Junction detection and grouping with probabilistic edge models and Bayesian \(A^{\ast}\)
- A decomposition-based approach to layered manufacturing
- Optimal Steiner hull algorithm
- Iterated snap rounding
- Center problems with pos/neg weights on trees
- Tight degree bounds for pseudo-triangulations of points
- Translating a regular grid over a point set
- The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra
- The visibility graph of congruent discs is Hamiltonian
- Anisotropic finite elements for the Stokes problem: a posteriori error estimator and adaptive mesh
- Lower bounds for intersection searching and fractional cascading in higher dimension
- Improved algorithms for placing undesirable facilities
- The 2-center problem in three dimensions
- Efficient computation of partition of unity interpolants through a block-based searching technique
- Markov models of coarsening in two-dimensional foams with edge rupture
- Adaptive radial basis function partition of unity interpolation: a bivariate algorithm for unstructured data
- Well-testing based turbidite lobes modeling using the ensemble smoother with multiple data assimilation
- A dynamical interval Newton method
- Computational and analytical bounds for multivariate Bernoulli distributions
- Geometric systems of unbiased representatives
- Geometric separability using orthogonal objects
- Optimal area polygonization problems: exact solutions through geometric duality
- Multidimensional segment trees can do range updates in poly-logarithmic time
- There are simple and robust refinements (almost) as good as Delaunay
- Towards untrimmed NURBS: CAD embedded reparameterization of trimmed B-rep geometry using frame-field guided global parameterization
- Reprint of: Delaunay refinement algorithms for triangular mesh generation
- Euclidean farthest-point Voronoi diagram of a digital edge
- Solution methods for a min-max facility location problem with regional customers considering closest Euclidean distances
- On farthest Voronoi cells
- An efficient cutting plane algorithm for the smallest enclosing circle problem
- An adaptable and extensible geometry kernel
- Patient-specific vascular NURBS modeling for isogeometric analysis of blood flow
- Partition of unity interpolation using stable kernel-based techniques
- Electoral strategies in a dynamical democratic system. Geometric models
- Locating a semi-obnoxious covering facility with repelling polygonal regions
- Voronoi diagram with visual restriction
- A practical approach to the 2D incremental nearest-point problem suitable for different point distributions
- An architecture independent study of parallel segment trees
- Covering points with a polygon
- Cost prediction for ray shooting in octrees
- Geometric filtering of pairwise atomic interactions applied to the design of efficient statistical potentials
- Faster core-set constructions and data-stream algorithms in fixed dimensions
- Estimating regions of absolute stability with the use of piecewise linear Lyapunov functions
- A functional language to implement the divide-and-conquer Delaunay triangulation algorithm
- An approach to the distributionally robust shortest path problem
- A radius of robust feasibility for uncertain farthest Voronoi cells
- Computational geometry in location
- Computational geometry on surfaces. Performing computational geometry on the cylinder, the sphere, the torus, and the cone
- A combinatorial algorithm to construct 3D isothetic covers
- scientific article; zbMATH DE number 3887061 (Why is no real title available?)
- scientific article; zbMATH DE number 4211464 (Why is no real title available?)
- Spatially-distributed coverage optimization and control with limited-range interactions
- Dilation-free graphs in thel1 metric
- Optimal Insertion of a Segment Highway in a City Metric
- Equal-Area Locus-Based Convex Polygon Decomposition
- Spanners of Additively Weighted Point Sets
- VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
- Introduction to applied geometry
- Computational Geometry Methods and Intelligent Computing
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- Minimum enclosing circle of a set of fixed points and a mobile point
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Algorithms for the edge-width of an embedded graph
- MEASURING GEOMETRIC COMPLEXITY OF 3D MODELS FOR FEATURE RECOGNITION
- Computational Geometry in C
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- scientific article; zbMATH DE number 1306029 (Why is no real title available?)
- scientific article; zbMATH DE number 589497 (Why is no real title available?)
This page was built for publication: Computational geometry. Algorithms and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4344150)
