Computational geometry. An introduction
This is the second printing (death-line in 1988) of a central and excellent book on computational geometry [first printing in 1985 by \textit{F. P. Preparata} and \textit{M. I. Shamos}, Text and monographs in computer science, New York, Springer-Verlag (1985; Zbl 0575.68059)]. Minor errors are corrected and additional comments are given. Also some new topics are discussed. Among others this are the following: The bridged chain method in geometric searching (optimal techniques), iterated search and fractional cascading, an expanded discussion of fractional cascading, and the linear-time construction of the Voronoi diagram of a convex polygon. In the meantime several other open questions have been solved, for instance optimal triangulation, so further work will be necessary to give an up-to-date third printing. Some new papers are added in the list of references.
- Semi-local longest common subsequences in subquadratic time
- Two-dimensional minimax Latin hypercube designs
- A fast algorithm for the alpha-connected two-center decision problem
- Linear-time algorithm for finding a maximum-density segment of a sequence
- On the complexity of crossings in permutations
- A simple factor-3 approximation for labeling points with circles
- Region-fault tolerant geometric spanners
- Fitting a C^m-smooth function to data. II
- The C^m norm of a function with prescribed jets. II
- Digitization scheme that assures faithful reconstruction of plane figures
- Algorithms for optimal outlier removal
- Optimal algorithm for a special point-labeling problem
- Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
- Finding the \(\Theta \)-guarded region
- Robustness of k-gon Voronoi diagram construction
- A linear time algorithm for obtaining the convex hull of a simple polygon
- Finding extreme points in three dimensions and solving the post-office problem in the plane
- Halfspace range search: An algorithmic application of k-sets
- Generalized Delaunay triangulation for planar graphs
- Computing relative neighbourhood graphs in the plane
- Finding transversals for sets of simple geometric figures
- On the use of composite grid schemes in computational aerodynamics
- Solving related two- and three-dimensional linear programming problems in logarithmic time
- Geometric containment and vector dominance
- A faster divide-and-conquer algorithm for constructing Delaunay triangulations
- Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
- A variant of Ben-Or's lower bound for algebraic decision trees
- Motion planning among time dependent obstacles
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- An O(n) algorithm for least squares quasi-convex approximation
- On the numerical condition of polynomials in Bernstein form
- On approximation behavior of the greedy triangulation for convex polygons
- Optimal piecewise linear motion of an object among obstacles
- On problem transformability in VLSI
- A sweepline algorithm for Voronoi diagrams
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Minimum polygonal separation
- Geometric optimization and the polynomial hierarchy
- Parallel algorithms for some functions of two convex polygons
- Decomposition and intersection of simple splinegons
- The expected size of some graphs in computational geometry
- Line arrangements and range search
- Obtaining lower bounds using artificial components
- An O(log n) time parallel algorithm for triangulating a set of points in the plane
- A linear expected-time algorithm for computing planar relative neighbourhood graphs
- A log log n data structure for three-sided range queries
- A non-Hamiltonian, nondegenerate Delaunay triangulation
- On O(\(\sqrt{n})\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors
- Establishing order in planar subdivisions
- An O(n log n) algorithm for the all-nearest-neighbors problem
- Parallel computational geometry
- Constrained Delaunay triangulations
- On the geodesic Voronoi diagram of point sites in a simple polygon
- L-infinity interdistance selection by parametric search
- An algorithmic approach to some problems in terrain navigation
- Circular discs containing eigenvalues of normal matrices
- A space efficient greedy triangulation algorithm
- A simple linear-time algorithm for computing the ring and MST of unimodal polygons
- A study on two geometric location problems
- An upper bound on the shortness exponent of inscribable polytopes
- A set operation algorithm for sculptured solids modeled with trimmed patches
- A note on lower bounds for the maximum area and maximum perimeter k-gon problems
- Approximating the diameter of a set of points in the Euclidean space
- Voronoi diagrams with barriers and the shortest diagonal problem
- Euclidean geometry in terms of automata theory
- Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems
- Solution approaches to irregular nesting problems
- Compaction and separation algorithms for non-convex polygons and their applications
- On the (n n) lower bound for convex hull and maximal vector determination
- A note on Delaunay and optimal triangulations
- Worst-case optimal insertion and deletion methods for decomposable searching problems
- Maintenance of configurations in the plane
- Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
- On the multimodality of distances in convex polygons
- Restricted-oriented convex sets
- Parallel computation of distance transforms
- Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays
- Computational geometry algorithms for the systolic screen
- Euclidean minimum spanning trees and bichromatic closest pairs
- Computing the convex hull in a hammock
- Computing the minimum Hausdorff distance between two point sets on a line under translation
- Computing dominances in E^ n
- On \(k\)-sets in arrangements of curves and surfaces
- Divided \(k-d\) trees
- Improved complexity bounds for location problems on the real line
- Fixed-radius near neighbors search
- A method for approximating the solution set of a system of convex inequalities by polytopes
- The excess-mass ellipsiod
- On the difficulty of triangulating three-dimensional nonconvex polyhedra
- Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
- On the complexity of the extreme points decision problem
- Satisfying general proximity/similarity queries with metric trees
- Delaunay triangulation of arbitrarily shaped planar domains
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Classes of graphs which approximate the complete Euclidean graph
- How to find Steiner minimal trees in Euclidean \(d\)-space
- Learning in parallel
- Optimal parallel algorithms for point-set and polygon problems
- Parallel computational geometry of rectangles
- Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers
This page was built for publication: Computational geometry. An introduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3992847)