scientific article
From MaRDI portal
Publication:3694703
zbMath0575.68059MaRDI QIDQ3694703
Michael Ian Shamos, Franco P. Preparata
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial aspects of finite geometries (05B25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01)
Related Items (only showing first 100 items - show all)
A provably fast linear-expected-time maxima-finding algorithm ⋮ Trajectory planning in \(H\)-space ⋮ An optimal algorithm for the on-line closest-pair problem ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Geometry of optimal value functions with applications to redundancy in linear programming ⋮ Constructing competitive tours from local information ⋮ A linear-time construction of the relative neighborhood graph from the Delaunay triangulation ⋮ Distance measures on intersecting objects and their applications ⋮ Unit-cost pointers versus logarithmic-cost addresses ⋮ Robust gift wrapping for the three-dimensional convex hull ⋮ Hashing lazy numbers ⋮ An algorithm to compute bounds for the star discrepancy ⋮ An introduction to randomization in computational geometry ⋮ A survey of constrained classification ⋮ Computational dynamics: Modeling and visualizing trajectory flows in phase space. ⋮ Time-optimal trajectories of a rod in the plane subject to velocity constraints ⋮ Sorting helps for Voronoi diagrams ⋮ Orthogonal queries in segments ⋮ On the area of intersection between two closed 2-D objects. ⋮ Theorem on four support vertices of a polygonal line ⋮ Multidimensional medians arising from geodesics on graphs ⋮ Simultaneous dominance representation of multiple posets ⋮ An analytical solution to the minimum \(L_ p\)-norm of a hyperplane ⋮ Algorithm to estimate the perimeter of a plane figure from its discretized image ⋮ Using domain decomposition to find graph bisectors ⋮ The biobjective absolute center problem ⋮ Characterizing and efficiently computing quadrangulations of planar point sets ⋮ Computing mixed volume and all mixed cells in quermassintegral time ⋮ Algorithmic graph embeddings ⋮ Compact location problems ⋮ Planar stage graphs: Characterizations and applications ⋮ Polynomial time algorithms for three-label point labeling. ⋮ Mutual exclusion in MANETs using quorum agreements ⋮ Sorting weighted distances with applications to objective function evaluations in single facility location problems. ⋮ On graphs preserving rectilinear shortest paths in the presence of obstacles ⋮ Steiner minimal trees for three points with one convex polygonal obstacle ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ On movable separability and isotheticity ⋮ A new representation and algorithm for constructing convex hulls in higher dimensional spaces ⋮ Efficient algorithms for the largest rectangle problem ⋮ Attribute grammars are useful for combinatorics ⋮ A convexity-preserving \(C^ 2\) parametric rational cubic interpolation ⋮ The application of \(\psi\)-transform for determining a near-optimal path in the presence of polyhedral obstacles ⋮ The convergence rate of the sandwich algorithm for approximating convex functions ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Fast algorithms for greedy triangulation ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ An automatic coarse and fine surface mesh generation scheme based on medial axis transform. I: Algorithms ⋮ GOSH: derivative-free global optimization using multi-dimensional space-filling curves ⋮ \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\) ⋮ Spanning trees in multipartite geometric graphs ⋮ Data structures for halfplane proximity queries and incremental Voronoi diagrams ⋮ Fast geometric approximation techniques and geometric embedding problems ⋮ Two \(P\)-complete problems in the theory of the reals ⋮ Duality of constrained Voronoi diagrams and Delaunay triangulations ⋮ Fast linear expected-time algorithms for computing maxima and convex hulls ⋮ Maximum \(k\)-covering of weighted transitive graphs with applications ⋮ Shortest curves in planar regions with curved boundary ⋮ On the randomized construction of the Delaunay tree ⋮ Efficient algorithms for the smallest enclosing ball problem ⋮ Structure of a simple scheduling polyhedron ⋮ An efficient algorithm for finding the CSG representation of a simple polygon ⋮ Planning a time-minimal motion among moving obstacles ⋮ Solving degenerate sparse polynomial systems faster ⋮ Testing the necklace condition for shortest tours and optimal factors in the plane ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Generalized halfspaces in restricted-orientation convexity ⋮ The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees ⋮ A nearly parallel algorithm for the Voronoi diagram of a convex polygon ⋮ Minimal binary trees with a regular boundary: The case of skeletons with five endpoints ⋮ Thinning algorithms for scattered data interpolation ⋮ Feasible real random access machines ⋮ Maximin location: Discretization not always works ⋮ Advances in the theory and practice of graph drawing ⋮ Watchman routes in the presence of a pair of convex polygons ⋮ Computing connectedness: disconnectedness and discreteness. ⋮ Asymptotics for the length of a minimal triangulation on a random sample ⋮ On the variance of the number of maxima in random vectors and its applications ⋮ Fast stabbing of boxes in high dimensions ⋮ From template analysis to generating partitions. I: Periodic orbits, knots and symbolic encodings ⋮ The finite volume method and application in combinations ⋮ Fuzzy distances for proximity characterization under uncertainty ⋮ An optimal algorithm for rectangle placement ⋮ Adaptivity techniques for compressible inviscid flows ⋮ Numerical stability of a convex hull algorithm for simple polygons ⋮ Analytic variations on quadtrees ⋮ On-line algorithms for locating checkpoints ⋮ Melting, pinning and forced flow of magnetic bubble arrays ⋮ Algorithms for bichromatic line-segment problems and polyhedral terrains ⋮ Approximation in VLSI simulation ⋮ Transforming triangulations in polygonal domains ⋮ Computation of the solutions of nonlinear polynomial systems ⋮ Algorithms for ordering unorganized points along parametrized curves ⋮ A new look at Euclid's second proposition ⋮ Parallel solutions to geometric problems in the scan model of computation ⋮ Foundation of a computable solid modelling. ⋮ Lipschitzian optimization without the Lipschitz constant ⋮ Optimal algorithms for complete linkage clustering in \(d\) dimensions ⋮ An improved technique for output-sensitive hidden surface removal ⋮ Visibility with a moving point of view
This page was built for publication:
