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
Geometric partitioning and robust ad-hoc network design, Exact algorithms for size constrained 2-clustering in the plane, An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width, The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric, Faster subsequence recognition in compressed strings, On the dynamization of data structures, In-place algorithms for computing (Layers of) maxima, Inequalities for curves of constant breadth, Computing the volume of the union of spheres, Recognizing polygons, or how to spy, Parallel algorithms for shortest path problems in polygons, On-line sorting of twisted sequences in linear time, Hamiltonian cycles in linear-convex supergrid graphs, Scanline algorithms on a grid, A new representation of orientable 2-manifold polygonal surfaces for geometric modelling, Optimal algorithms for some polygon enclosure problems for VLSI layout analysis, (Approximate) uncertain skylines, Approximate covering detection among content-based subscriptions using space filling curves, Algorithmic aspects of intersection graphs and representation hypergraphs, Maintaining range trees in secondary memory. Part I: Partitions, Systolic algorithms for computational geometry problems - a survey, Stable marker-particle method for the Voronoi diagram in a flow field, Fat arcs: A bounding region with cubic convergence, Topologically sweeping an arrangement, Euclidean geometry in terms of automata theory, An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing, Bounded flatness in \(Q\)-triangulated regular \(n\)-simplexes, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, Approximate polytope ensemble for one-class classification, Guarding a set of line segments in the plane, A faster circle-sweep Delaunay triangulation algorithm, Graph problems arising from parameter identification of discrete dynamical systems, A Pre-Processed Cross Link Detection Protocol for geographic routing in mobile ad hoc and sensor networks under realistic environments with obstacles, A sublogarithmic convex hull algorithm, Storing line segments in partition trees, The Bernstein polynomial basis: a centennial retrospective, Hidden surface removal for rectangles, An efficient and numerically correct algorithm for the 2D convex hull problem, A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments, Augmenting the edge connectivity of planar straight line graphs to three, A volume first maxima-finding algorithm, A new algorithm for computing the convex hull of a planar point set, A faster algorithm for computing motorcycle graphs, The two variable per inequality abstract domain, Minimum Hausdorff distance under rigid motions and comparison of protein structures, Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays, A result about the power of geometric oracle machines, A weak characterisation of the Delaunay triangulation, Blaschke-type theorem and separation of disjoint closed geodesic convex sets, Minimal length tree networks on the unit sphere, A parallel algorithm based on convexity for the computing of Delaunay tessellation, Algorithms for deciding the containment of polygons, On input read-modes of alternating Turing machines, Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions, A note on the combinatorial structure of the visibility graph in simple polygons, Boundedness of level lines for two-dimensional random fields, Proximity problems for points on a rectilinear plane with rectangular obstacles, Randomized quickhull, Barycentric coordinates for convex polytopes, On counting pairs of intersecting segments and off-line triangle range searching, Piecewise linear interpolants to Lagrange and Hermite convex scattered data, A data modeling abstraction for describing triangular mesh algorithms, Improved subquadratic 3SUM, On the polyhedral complexity of the integer points in a hyperball, Opaque sets, Finite nondense point set analysis, Orienting polygonal parts without sensors, A generalized hypergreedy algorithm for weighted perfect matching, Efficiently updating constrained Delaunay triangulations, A parallel algorithm to construct a dominance graph on nonoverlapping rectangles, The indecomposability problem in binary morphology: an algebraic approach, Mathematical morphological operations of boundary-represented geometric objects., Local tests for consistency of support hyperplane data., Line facility location in weighted regions, On the asymptotics of trimmed best \(k\)-nets, On covering problems of Rado, Ectropy of diversity measures for populations in Euclidean space, Coupled path planning, region optimization, and applications in intensity-modulated radiation therapy, An almost space-optimal streaming algorithm for coresets in fixed dimensions, Dynamic computational geometry on meshes and hypercubes, An optimal algorithm for one-separation of a set of isothetic polygons, Categorization generated by extended prototypes -- an axiomatic approach, Delaunay-based derivative-free optimization via global surrogates. II: Convex constraints, Active sampling for multiple output identification, A discrete element approach to evaluate stresses due to line loading on an elastic half-space, Construction of Voronoi diagrams in the plane by using maps, A univariate global search working with a set of Lipschitz constants for the first derivative, A dual approach to detect polyhedral intersections in arbitrary dimensions, Properties of a method for polyhedral approximation of the feasible criterion set in convex multiobjective problems, A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\), A fuzzy model for linear regression, On a circle placement problem, Finding minimal nested polygons, Dynamic partition trees, Surfaces over Dirichlet tessellations, Using Gale transforms in computational geometry, Construction of three-dimensional Delaunay triangulations using local transformations, Rectifiable sets and the traveling salesman problem, Approximate \(k\)-closest-pairs in large high-dimensional data sets, Grid refinement in the construction of Lyapunov functions using radial basis functions, A fuzzy approach to visibility maps creation over digital terrains., Efficient construction of a bounded-degree spanner with low weight, A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, The searching over separators strategy to solve some NP-hard problems in subexponential time, Selecting distances in the plane, Computing the intersection-depth to polyhedra, Constructing strongly convex approximate hulls with inaccurate primitives, Algorithms for projecting points to give the most uniform distribution with applications to hashing, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Competitive facility location: the Voronoi game, Comparison of continuity equation and Gaussian mixture model for long-term density propagation using semi-analytical methods, An efficient inexact Newton-CG algorithm for the smallest enclosing ball problem of large dimensions, Point set pattern matching in \(d\)-dimensions, Approximating minimum-cost graph problems with spanning tree edges, Assembly sequences for polyhedra, Sequent reconstruction in LLM -- A sweepline proof, Using geometry to solve the transportation problem in the plane, Landmark-based robot navigation, Staircase visibility and computation of kernels, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids, Dissimilarity measures for population-based global optimization algorithms, Automatic unstructured grid generation based on iterative point insertion, Helix splines as an example of affine Tchebycheffian splines, A planar minimax algorithm for analysis of coordinate measurements, A note on finding extreme points in multivariate space, The nesting problem in the leather manufacturing industry, A linear-time algorithm for constructing a circular visibility diagram, Balancing minimum spanning trees and shortest-path trees, A time-optimal parallel algorithm for three-dimensional convex hulls, A framework for advancing front techniques of finite element mesh generation, On the \(k\)-colored rainbow sets in fixed dimensions, Euclidean Voronoi diagrams of 3D spheres and applications to protein structure analysis, Percolation of level sets for two-dimensional random fields with lattice symmetry, Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees, Sweep methods for parallel computational geometry, Optimal cooperative search in fractional cascaded data structures, Incremental topological flipping works for regular triangulations, Lower bounds for arithmetic networks. II: Sum of Betti numbers, Designing checkers for programs that run in parallel, Mapping 3-D IIR digital filter onto systolic arrays, Optimizing area for three-layer knock-knee channel routing, Improved heuristics for the minimum weight triangulation problem, Detection of rotational and involutional symmetries and congruity of polyhedra, Collision avoidance for mobile robots with limited sensing and limited information about moving obstacles, Connected component and simple polygon intersection searching, A fast algorithm for point-location in a finite element mesh, Multidimensional frontier visualization based on optimization methods using parallel computations, Characterizing proximity trees, On stable line segments in all triangulations of a planar point set, An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem, Efficient sampling methods for discrete distributions, Relations between FEM and FVM applied to the Poisson equation, Subquadratic algorithms for algebraic 3SUM, Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back, Supervised box clustering, Efficient observer-dependent simplification in polygonal domains, Quantum speed-up for unsupervised learning, Improved bounds for finger search on a RAM, Similarity of polygonal curves in the presence of outliers, The smooth metric in the class of plane figures with piecewise-convex and concave boundary. I, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Three-dimensional convex hull as a fruitful source of diagrams, Minimax optimal placement problem for special-form objects on a multiply connected domain, Covering paths for planar point sets, A fully general, exact algorithm for nesting irregular shapes, A combinatorial theorem on labeling squares with points and its application, Construction of the nearest neighbor embracing graph of a point set, Shiftable intervals, All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time, Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings, Triangulating with high connectivity., Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\)., Fast greedy triangulation algorithms., Surface order scaling in stochastic geometry, Parametric search: three new applications, A sweep-line algorithm for the inclusion hierarchy among circles, Cluster-based outlier detection, On the restricted 1-Steiner tree problem, Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball, An improved algorithm for finding the closest pair of points, Coverage and exposure paths in wireless sensor networks, Mathematical modeling of interactions of primary geometric 3D objects, Active-learning a convex body in low dimensions, Generating rooted triangulations without repetitions, A real-time system-adapted anomaly detector, A decompositin theorem for convexity spaces, General models in min-max planar location: Checking optimality conditions, Simultaneous mesh generation and partitioning for Delaunay meshes, Application of the theory of optimal set partitioning for constructing fuzzy Voronoi diagrams, On approximation ratios of minimum-energy multicast routing in wireless networks, Simultaneous uniqueness of infinite clusters in stationary random labeled graphs, Robot motion planning and the single cell problem in arrangements, A characterization theorem and an algorithm for a convex hull problem, Locating two obnoxious facilities using the weighted maximin criterion, Isoperimetric enclosures, On constant factors in comparison-based geometric algorithms and data structures, Four-connected triangulations of planar point sets, The approximate rectangle of influence drawability problem, A fixed-parameter algorithm for guarding 1.5D terrains, 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, Continuous operator method application for direct and inverse scattering problems, Shape-understanding system: A system of experts, Time-discretized variational formulation of non-smooth frictional contact, Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations, One-to-one piecewise linear mappings over triangulations, Verification of Closest Pair of Points Algorithms, Discretization of the 3d monge−ampere operator, between wide stencils and power diagrams, ASPECTS OF 2-D DELAUNAY MESH GENERATION, Dynamic closest pairs — A probabilistic approach, Multidimensional binary partitions: distributed data structures for spatial partitioning, Generalized Qualitative Spatio-Temporal Reasoning: Complexity and Tableau Method, An optimal algorithm for finding the separation of simple polygons, Filling polyhedral molds, Scalable algorithms for bichromatic line segment intersection problems on Coarse Grained Multicomputers, A complete and efficient algorithm for the intersection of a general and a convex polyhedron, Computing the smallest k-enclosing circle and related problems, Counting and reporting red/blue segment intersections, Computing Simple Paths on Points in Simple Polygons, Divide and Conquer Method for k-Set Polygons, Approximation Algorithms for Buy-at-Bulk Geometric Network Design, Constructing the minimization diagram of a two-parameter problem, An algorithm for generalized point location and its applications, The convex hull of a set of convex polygons, A straightforward algorithm for computing the medial axis of a simple polygon, Constructing sets of functions which have a givenF-cardinality, The minimal size of a square which includes a digital convex 2K–gon, Unnamed Item, TIME-OPTIMAL GEOMETRIC ALGORITHMS IN HYPERCUBIC NETWORKS, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, ANALOG PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY, Smoothing the Gap Between NP and ER, Regular triangulations and Steiner points, On farthest Bregman Voronoi cells, Efficient Data Structures for the Orthogonal Range Successor Problem, Directional Geometric Routing on Mobile Ad Hoc Networks, Ranking intervals under visibility constraints∗, Constructing bimodal convex hexagons, General circular permutation layout, Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes, Parallel computation of discrete Voronoi diagrams, An efficient algorithm for shortest paths in vertical and horizontal segments, Position-independent near optimal searching and on-line recognition in star polygons, Computing constrained minimum-width annuli of point sets, Graded tetrahedral finite element meshes, Triangle-Based Heuristics for Area Optimal Polygonizations, Geometric p-Center Problems with Centers Constrained to Two Lines, The $\beta$-Delaunay tessellation III: Kendall's problem and limit theorems in high dimensions, Modified refinement algorithm to construct Lyapunov functions using meshless collocation, Improved algorithms for determining the injectivity of 2D and 3D rational Bézier curves, A radius of robust feasibility for uncertain farthest Voronoi cells, On the complexity of convex hull algorithms if rotational minima can be found very fast, Geometry and topology of local minimal 2-trees, Unnamed Item, Multiple point visibility and related problems, An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane, On Vertex- and Empty-Ply Proximity Drawings, A New Heuristic for Minimum Weight Triangulation, Covering Polygons with Rectangles, On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model, Unnamed Item, Rectilinear Convex Hull with Minimum Area, Construction of 3D Orthogonal Cover of a Digital Object, On Some Geometric Problems of Color-Spanning Sets, Minimum Width Rectangular Annulus, On creativity of slime mould, Linear time computation of feasible regions for robust compensators, Identifying genuine clusters in a classification, Node-based uniform strain elements for three-node triangular and four-node tetrahedral meshes, Shortest-path queries in static networks, Process planning for multi-axis NC machining of free surfaces, DETERMINING THE SHAPE OF A PATTERN CLASS: EXTENSION TO RN, Optimal $N$-term approximation by linear splines over anisotropic Delaunay triangulations, Unnamed Item, Unnamed Item, A Separator Theorem for String Graphs and its Applications, A Separator Theorem for String Graphs and Its Applications, On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem, Improved Algorithm for Maximum Independent Set on Unit Disk Graph, A Direct Method for Determining the Lower Convex Hull of a Finite Point Set in 3D, Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP, On Geometric Set Cover for Orthants, Consistent digital curved rays and pseudoline arrangements, Unnamed Item, Opaque Sets, Line Segment Facility Location in Weighted Subdivisions, The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension, A Lower Bound for Computing Lagrange’s Real Root Bound, Generation of 2D Conforming Voronoi Diagram in Complex Domain, On Three Constrained Versions of the Digital Circular Arc Recognition Problem, Density-based O-Means clustering algorithm using minimum spanning tree, Optimality of the Methods for Approximating the Feasible Criterion Set in the Convex Case, On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, Hamiltonian cycles in planar triangulations with no separating triangles, Geometric optimization and sums of algebraic functions, Unnamed Item, Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay, A CAD/CAPP interface for complex rotationally symmetric parts, On Some Proximity Problems of Colored Sets, Observation of a hexatic vortex glass in flux lattices of the high-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="italic">T</mml:mi></mml:mrow><mml:mrow><mml:mi mathvariant="italic">c</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math>superconductor<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">Bi</mml:mi></mml:mrow><mml:mrow><mml:…, Polygon-based contact resolution for superquadrics, Efficient randomized incremental algorithm for the closest pair problem using Leafary trees, Compact location problems with budget and communication constraints, Efficient computation of the geodesic Voronoi diagram of points in a simple polygon, Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time, Fast skeleton construction, On reconfiguration graphs of independent sets under token sliding, Complexity and approximability of certain bicriteria location problems, An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons, Graph ear decompositions and graph embeddings, Algorithmic graph embeddings, An efficient algorithm for the three-dimensional diameter problem, Analysis of two-step index structure for complex spatial objects, An efficient algorithm for computing the maximum empty rectangle in three dimensions, Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology, Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry, On point covers of \(c-\)oriented polygons, Fast algorithms for computing \(\beta\)-skeletons and their relatives., Shape skeletonization by identifying discrete local symmetries, Distributed distance-\(r\) covering problems on sparse high-girth graphs, Tracing compressed curves in triangulated surfaces
