scientific article
From MaRDI portal
zbMath0759.68037MaRDI QIDQ3992847
Michael Ian Shamos, Franco P. Preparata
Publication date: 23 January 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Building bridges between convex regions, On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, TuringMobile: a Turing machine of oblivious mobile robots with limited visibility and its applications, Global \(C^{1,\alpha}\) regularity for Monge-Ampère equation and convex envelope, Simplicial mesh of an arbitrary polyhedron., On a variation of the box-counting method for the numerical determination of the fractal dimension of a subset in 2D space, Silhouette vectorization by affine scale-space, Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing, Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\), Optimal area polygonization problems: exact solutions through geometric duality, Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains, Negative results on characterizing visibility graphs, Separation and approximation of polyhedral objects, Vertex-to-point conflict-free chromatic guarding is NP-hard, On a class of \(O(n^ 2)\) problems in computational geometry, Optimal conditions for connectedness of discretized sets, Linear-size nonobtuse triangulation of polygons, Efficient piecewise-linear function approximation using the uniform metric, Almost optimal set covers in finite VC-dimension, Vertical decompositions for triangles in 3-space, A compact piecewise-linear Voronoi diagram for convex sites in the plane, Combining recursive spatial decompositions and domain Delaunay tetrahedrizations for meshing arbitrarily shaped curved solid models, Voronoi-like partition of lattice in cellular automata, Computing depth orders for fat objects and related problems, Average case analysis of dynamic geometric optimization, Determining bar-representability for ordered weighted graphs, Computing grasp functions, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, K-dominance in multidimensional data: theory and applications, Integrating CAD and numerical analysis: `dirty geometry' handling using the finite cell method, Quasi-Monte-Carlo methods and the dispersion of point sequences, Mixed-volume computation by dynamic lifting applied to polynomial system solving, An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\), Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon, Generating random polygons with given vertices, All convex polyhedra can be clamped with parallel jaw grippers, A novel approach to generating microstructurally-aware non-convex domains, Improved algorithms for placing undesirable facilities, Selected computational aspects of the meshless finite difference method, Starshaped sets, Maximum packing for biconnected outerplanar graphs, Algorithms for the decomposition of a polygon into convex polygons, Application of NEM in seepage analysis with a free surface, Zone theorem for arrangements in dimension three, Extracting Boolean and probabilistic rules from trained neural networks, Largest and smallest area triangles on imprecise points, Efficiency evaluation in data envelopment analysis using strong defining hyperplanes. A cross-efficiency framework, Computational aspects of the colorful Carathéodory theorem, Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Reporting and counting maximal points in a query orthogonal rectangle, Euclidean farthest-point Voronoi diagram of a digital edge, Two-dimensional closest pair problem: a closer look, Shape of an arbitrary finite point set in \(\mathbb{R}^2\), Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations, Selected applications of linear semi-infinite systems theory, Well-testing based turbidite lobes modeling using the ensemble smoother with multiple data assimilation, An estimate for the Hausdorff distance between a set and its convex hull in Euclidean spaces of small dimension, QuickhullDisk: a faster convex hull algorithm for disks, Maximum spanning trees in normed planes, Efficient algorithms for support path with time constraint, Near optimal minimal convex hulls of disks, An approximate algorithm for the minimal vertex nested polygon problem, A sparse graph almost as good as the complete graph on points in \(k\) dimensions, Multistep scattered data interpolation using compactly supported radial basis functions, Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, The determinantal conjecture and Hadamard type inequalities, Triangulating point sets in space, New applications of random sampling in computational geometry, On the number of line separations of a finite set in the plane, Congruence, similarity, and symmetries of geometric objects, Computing geodesic furthest neighbors in simple polygons, Polyhedral line transversals in space, Applications of random sampling in computational geometry. II, A fast Las Vegas algorithm for triangulating a simple polygon, Quasi-optimal range searching in spaces of finite VC-dimension, There are planar graphs almost as good as the complete graph, Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros, On the average number of maximal in a set of vectors, Does a point lie inside a polygon ?, On guaranteed estimates of the area of convex subsets of compact sets on the plane, Efficient CAD-integrated isogeometric analysis of trimmed solids, Intersections and circuits in sets of line segments, On the restricted \(k\)-Steiner tree problem, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane, Approximation algorithms for lawn mowing and milling, Complexity of projected images of convex subdivisions, A solution of inverse problem in the theory of supercritical fluid extraction of oil from ground plant material, Efficient minimum spanning tree construction with Delaynay triangulation, On computing the diameter of a point set in high dimensional Euclidean space., The geometry of linear infeasibility, Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems, Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects, An external memory data structure for shortest path queries, Voronoi diagrams on the sphere, Translating a convex polyhedron over monotone polyhedra, On embedding an outer-planar graph in a point set, Efficient visibility queries in simple polygons, The interplay between cell adhesion and environment rigidity in the morphology of tumors, Fast approximations for sums of distances, clustering and the Fermat-Weber problem, 2-point site Voronoi diagrams, Shattering a set of objects in 2D, Asymptotics for Voronoi tessellations on random samples, Simpler proof of a realizability theorem on Delaunay triangulations, Boundary element color interpolation for instrumentation, imaging and internet graphics industries, Computing the smallest \(k\)-enclosing circle and related problems, Approximate decision algorithms for point set congruence, On range searching with semialgebraic sets, Computing minimum length paths of a given homotopy class, Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions, Moldable and castable polygons, Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\), On lines missing polyhedral sets in 3-space, Computing convex hull in a floating point arithmetic, Extracting and representing qualitative behaviors of complex systems in phase space, Toward the fast blind docking of a peptide to a target protein by using a four-body statistical pseudo-potential, Geometric clustering in normed planes, On the complexity of some basic problems in computational convexity. I. Containment problems, Recursive characterization of computable real-valued functions and relations, Approximate single linkage cluster analysis of large data sets in high-dimensional spaces, Drawing outerplanar minimum weight triangulations, On two-processor scheduling and maximum matching in permutation graphs, Monte Carlo approximation of form factors with error bounded a priori, Accelerated robust Boolean operations based on hybrid representations, Graph-theoretical conditions for inscribability and Delaunay realizability, On bicriterion minimal spanning trees: An approximation, Biological growth on a surface, A bird's eye-view of min-max and max-min functionals, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, On fast planning of suboptimal paths amidst polygonal obstacles in plane, On bandwidth selection using minimal spanning tree for kernel density estimation, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, New results on binary space partitions in the plane, Numerical approximations of generalized solutions of the Hamilton-Jacobi equations, Generalized multiple scale reproducing kernel particle methods, Three-dimensional unstructured mesh generation. I: Fundamental aspects of triangulation and point creation, Fundamentals of restricted-orientation convexity, A new algorithm for the two-polygon containment problem, Fine-grain discrete Voronoi diagram algorithms in \(L_1\) and \(L_\infty\) norms, Algorithms for constructing optimal \(n\)-networks in metric spaces, On fat partitioning, fat covering and the union size of polygons, Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep, Combinatorial aspects of geometric graphs, Dynamics and limiting behavior of Julia sets of König's method for multiple roots, The rectangle of influence drawability problem, Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\), Illumination by floodlights, Qualitative representation of positional information, Parametrization and smooth approximation of surface triangulations, A data structure for lattice representation, Getting around a lower bound for the minimum Hausdorff distance, Computing farthest neighbors on a convex polytope., A mesh-based partition of unity method for discontinuity modeling, Algorithms for testing occurrences of length 4 patterns in permutations, Colored spanning graphs for set visualization, On the \(\mathcal{O}_\beta\)-hull of a planar point set, Remarks on the computation of the horizon of a digital terrain, Minimal spanning trees on infinite sets, Searching and on-line recognition of star-shaped polygons., A resistor interpretation of general anisotropic cardiac tissue., Overview and recent advances in natural neighbour Galerkin methods, Normal approximation for stabilizing functionals, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, On the number of maximum empty boxes amidst \(n\) points, Fuzzy clustering using the convex hull as geometrical model, The geometry of carpentry and joinery, An algorithm for discrete approximation by quasi-convex functions on \(R^m\), About Delaunay triangulations and discrete maximum principles for the linear conforming FEM applied to the Poisson equation., Considering the attractor structure of chaotic maps for observer-based synchronization problems, Recent progress in exact geometric computation, Facility location problems with uncertainty on the plane, The multipoint Morisita index for the analysis of spatial patterns, Constructing arrangements optimally in parallel, Constructing the convex hull of a partially sorted set of points, Local search for the Steiner tree problem in the Euclidean plane, Undesirable facility location with minimal covering objectives, Numerical construction of optimal adaptive grids in two spatial dimensions, A constrained minimum spanning tree problem, The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules, Chromatic nearest neighbor searching: A query sensitive approach, Approximate range searching, Approximating the noninferior set in multiobjective linear programming problems, Performance evaluation of evolutionary class of algorithms -- an application to 0-1 knapsack problem, Sorting and computing convex hulls on processor arrays with reconfigurable bus systems, A new representation of binary search trees, The new \(k\)-windows algorithm for improving the \(k\)-means clustering algorithm, The rooted tree embedding problem into points in the plane, The complexity of finding minimal Voronoi covers with applications to machine learning, Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs, Improving continuity of Voronoi-based interpolation over Delaunay spheres, Optimal computation of the Voronoi diagram of disjoint clusters, On computing the optimal bridge between two convex polygons., Space-time trade-offs for some ranking and searching queries, Lower bounds for approximate polygon decomposition and minimum gap, Bounds for the Element Distinctness Problem on one-tape Turing machines, Regular triangulations of dynamic sets of points, On optimal bridges between two convex regions, Experimental results on quadrangulations of sets of fixed points, On a theorem of Wielandt and the compounds of unitary matrices, Adaptive thinning for bivariate scattered data, A lower bound for computing geometric spanners, Optimization of the Hausdorff distance between sets in Euclidean space, Minimally separating sets, mediatrices, and Brillouin spaces, Fifty new invariants of \(N\)-periodics in the elliptic billiard, A linear optimization oracle for zonotope computation, An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\), Computation of spatial skyline points, Dynamic layers of maxima with applications to dominating queries, Diagonal generalizaton of the DIRECT method for problems with constraints, An improved algorithm for intersecting convex polygons, On building the transitive reduction of a two-dimensional poset, Detecting conjunctions of global predicates, Towards optimal two-dimensional indexing for constraint databases, A note on approximating graph genus, Computing minimum-area rectilinear convex hull and \(L\)-shape, Gift-wrapping based preimage computation algorithm, Tangential cover for thick digital curves, Sparse dominance queries for many points in optimal time and space, A polynomial time solution for labeling a rectilinear map, Maintaining visibility of a polygon with a moving point of view, Parity OBDDs cannot be handled efficiently enough, HCPO: an efficient insertion order for incremental Delaunay triangulation, A note on maximum independent set and related problems on box graphs, Computing the optimal bridge between two convex polygons, Triangulations without minimum-weight drawing, A lower bound for approximating the geometric minimum weight matching, Covering a set of points by two axis-parallel boxes, On the all-farthest-segments problem for a planar set of points, Setting defect charts control limits to balance cycle time and yield for a tandem production line, Efficient heuristic algorithms for maximum utility product pricing problems, Space-efficient planar convex hull algorithms, Long non-crossing configurations in the plane, One-dimensional approximate point set pattern matching with \(L_p\)-norm, Euclidean chains and their shortcuts, All-maximum and all-minimum problems under some measures, Improved data structures for the orthogonal range successor problem, On the stretch factor of Delaunay triangulations of points in convex position, Shape elongation from optimal encasing rectangles, Computing convex quadrangulations, On a class of \(O(n^2)\) problems in computational geometry, Optimal partition trees, Energy-conserving contact interaction models for arbitrarily shaped discrete elements, A quasi steady state method for solving transient Darcy flow in complex 3D fractured networks, Maxima-finding algorithms for multidimensional samples: A two-phase approach, Efficient view point selection for silhouettes of convex polyhedra, Reconstructing orthogonal polyhedra from putative vertex sets, Conservative interpolation between volume meshes by local Galerkin projection, Certifying algorithms, Output-sensitive peeling of convex and maximal layers, The Hamiltonian properties of supergrid graphs, The legacy of automatic mesh generation from solid modeling, Why is the 3D Delaunay triangulation difficult to construct?, Tangent, normal, and visibility cones on Bézier surfaces, Gray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions, Fast randomized parallel methods for planar convex hull construction, Finding a shortest diagonal of a simple polygon in linear time, Visibility graphs of towers, Sequential and parallel algorithms for finding a maximum convex polygon, Towards exact geometric computation, Geometric pattern matching under Euclidean motion, Finding the largest area axis-parallel rectangle in a polygon, Range searching with efficient hierarchical cuttings, An upper bound for conforming Delaunay triangulations, Top-\(k\) Manhattan spatial skyline queries, An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object, Reconstructing sets of orthogonal line segments in the plane, Efficient algorithms for the conditional covering problem, Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach, Polynomial root-finding methods whose basins of attraction approximate Voronoi diagram, Planar expropriation problem with non-rigid rectangular facilities, A characterization of computable analysis on unbounded domains using differential equations, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, Some problems in distributed computational geometry, Finding the upper envelope of n line segments in O(n log n) time, The complexity and construction of many faces in arrangements of lines and of segments, Estimates for the minimal width of polytopes inscribed in convex bodies, Delaunay graphs are almost as good as complete graphs, Finding an Euclidean anti-\(k\)-centrum location of a set of points, Measure of circularity for parts of digital boundaries and its fast computation, Maximizing the number of obnoxious facilities to locate within a bounded region, On the modality of convex polygons, Upper bounds on geometric permutations for convex sets, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, A simple algorithm for computing the smallest enclosing circle, An incremental reconstruction method for dynamic planar point location, Automatic analysis of one-parameter planar ordinary differential equations by intelligent numeric simulation, The intersection searching problem for c-oriented polygons, Bisectors of linearly separable sets, Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy, On exact solutions to the Euclidean bottleneck Steiner tree problem, On the longest spanning tree with neighborhoods, A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form, On the maximum empty rectangle problem, On the definition and computation of rectilinear convex hulls, Convex hulls of objects bounded by algebraic curves, On sorting triangles in a Delaunay tessellation, Toughness and Delaunay triangulations, On levels in arrangements and Voronoi diagrams, Implementation of an adaptive algorithm for Richardson's method, Metric trees, 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, Affine invariant comparison of point-sets using convex hulls and Hausdorff distances, 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 intersection-sensitive algorithm for snap rounding, An algorithmic approach to some problems in terrain navigation, Circular discs containing eigenvalues of normal matrices, Digital planarity -- a review, Generators, extremals and bases of max cones, Finding shortest path in the presence of barriers: an alternate approach, 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, Parametric multiple sequence alignment and phylogeny construction, A simple algorithm for digital line recognition in the general case, Selecting distances in arrangements of hyperplanes spanned by points., Packing two disks into a polygonal environment., On the edge crossing properties of Euclidean minimum weight Laman graphs, Convex blocking and partial orders on the plane, Dynamic fractional cascading, Finding nearest neighbors with Voronoi tessellations, A straightforward iterative algorithm for the planar Voronoi diagram, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Computing Euclidean maximum spanning trees, Realizability of Delaunay triangulations, Dynamic maintenance of planar digraphs, with applications, Applications of generalized matrix searching to geometric algorithms, Triangulating a nonconvex polytope, Dynamic planar point location with optimal query time, An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs, Finding Hamiltonian cycles in certain planar graphs, Combinatorial complexity bounds for arrangements of curves and spheres, Coloring certain proximity graphs, Efficient dynamic algorithms for some geometric intersection problems, Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm, The upper envelope of piecewise linear functions: Algorithms and applications, Partitioning arrangements of lines. II: Applications, Generalized Delaunay triangulations of non-convex domains, Finding the conditional location of a median path on a tree, An algorithm for the difference between set covers, The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing, Solving continuous location-districting problems with Voronoi diagrams, A research note on design of fair surfaces over irregular domains using data-dependent triangulation, Some theoretical challenges in digital geometry: a perspective, Image deformations are better than optical flow, Largest empty circle centered on a query line, Approximating nearest neighbor among triangles in convex position, Convex drawings of hierarchical planar graphs and clustered planar graphs, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, 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, 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 \(\Omega (n\log 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, Optimal randomized parallel algorithms for computational geometry, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Maintaining the minimal distance of a point set in polylogarithmic time, Off-line dynamic maintenance of the width of a planar point set, Parallel rectilinear shortest paths with rectangular obstacles, Automatic mesh generator with specified boundary, On the covering multiplicity of lattices, Hidden surface removal for \(c\)-oriented polyhedra, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, A framework for 1-D compaction with forbidden region avoidance, Output-sensitive generation of the perspective view of isothetic parallelepipeds, On the parallel-decomposability of geometric problems, There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees, The use of domains in multicriteria decision making, GBSSS: The generalized big square small square method for planar single- facility location, Dynamic output-sensitive hidden surface removal for \(c\)-oriented polyhedra, Parallel fractional cascading on hypercube multiprocessors, Multiple objective analysis of long-term development strategies for a national economy, Computing the minimum weight triangulation of a set of linearly ordered points, Optimal time bounds for some proximity problems in the plane, Fully dynamic Delaunay triangulation in logarithmic expected per operation, Upper envelope onion peeling, Minimizing the sum of diameters efficiently, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Geometric medians, Parallel methods for visibility and shortest-path problems in simple polygons, Determination of minimum number of sensors and their locations for an automated facility: An algorithmic approach, Algorithms for computing centroids, The furthest-site geodesic Voronoi diagram, The upper envelope of Voronoi surfaces and its applications, Efficient hidden surface removal for objects with small union size, Degree constrained tree embedding into points in the plane, Circular permutation graph family with applications, On the optimal binary plane partition for sets of isothetic rectangles, Point location in fat subdivisions, On the randomized construction of the Delaunay tree, On-line computation of convolutions, Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra, Testing the necklace condition for shortest tours and optimal factors in the plane, Implicitly representing arrangements of lines or segments, Heuristics for optimum binary search trees and minimum weight triangulation problems, A refined model of computation for continuous problems, A perturbation scheme for spherical arrangements with application to molecular modeling, Optimal placement of convex polygons to maximize point containment, A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space, On determining optimal strategies in pursuit games in the plane, Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)], Growing methods for constructing Recursive Deterministic Perceptron neural networks and knowledge extraction, Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time, Developing scheduling systems for Daewoo shipbuilding: DAS project, Locational optimization problems solved through Voronoi diagrams, Equivalences between data envelopment analysis and the theory of redundancy in linear systems, On approximate and algebraic computability over the real numbers, An approximate algorithm for computing multidimensional convex hulls, How to morph tilings injectively, A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works, Mining optimized association rules for numeric attributes, The expected number of \(k\)-faces of a Voronoi diagram, Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study, On the optimal separating hyperplane for arbitrary sets: a generalization of the SVM formulation and a convex hull approach, On the arrangement of stochastic lines in \(\mathbb{R}^2\), Inconsistency analysis by approximately specified priorities, How many maxima can there be?, A simple algorithm for enumerating longest distances in the plane, Identifying parent locations in the Neyman-Scott process using Delaunay triangulation, Constructing competitive tours from local information, An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram, On certain Hamiltonian inner triangulations, Voronoi diagrams over dynamic scenes, Edge insertion for optimal triangulations, An efficient algorithm for the smallest enclosing ball problem in high dimensions, A heuristic algorithm for minimax sensor location in the plane, Advanced programming techniques applied to CGAL's arrangement package, A fast heuristic for approximating the minimum weight triangulation, Neighbours on a grid, An optimal algorithm for computing visible nearest foreign neighbors among colored line segments, On determining optimal strategies in pursuit games in the plane, Note on covering monotone orthogonal polygons with star-shaped polygons, Flying over a polyhedral terrain, A note on optimal floodlight illumination of stages, On the two-dimensional Davenport-Schinzel problem, Non-convex contour reconstruction, Tetrahedrizing point sets in three dimensions, The geometry of nesting problems: a tutorial, Good triangulations yield good tours, Monte-Carlo Valuation of American Options: Facts and New Algorithms to Improve Existing Methods, Single equation without inequalities to represent a composite curve, A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs, On some geometric problems of color-spanning sets, Abductive Reasoning in 2D Geospatial Problems, Generalization of the multipoint meshless FDM application to the nonlinear analysis, A penalty method for the identification of nonlinear elliptic differential operator, On geometric automata which can nondeterministically choose auxiliary points, Optimistic optimization for continuous nonconvex piecewise affine functions, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, Spanners for Directed Transmission Graphs, A note on the linearity of Ratliff and Rosenthal's algorithm for optimal picker routing, A fast and efficient algorithm for determining the connected orthogonal convex hulls, Optimal One-Dimensional Coverage by Unreliable Sensors, Understanding positioning from multiple images, Packing convex polygons in minimum-perimeter convex hulls, Computation over algebraic structures and a classification of undecidable problems, Multiway spatial joins, Unnamed Item, Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance, Line Facility Location in Weighted Regions, Simplified Planar Coresets for Data Streams, Three problems about simple polygons, Electoral strategies in a dynamical democratic system. Geometric models, Separating bichromatic point sets in the plane by restricted orientation convex hulls, Unique decomposition of homogeneous languages and application to isothetic regions, A simple method for resolving degeneracies in Delaunay triangulations, Algorithms for bivariate zonoid depth, Density Independent Algorithms for Sparsifying k-Step Random Walks, A practical approach to the 2D incremental nearest-point problem suitable for different point distributions, Polygon placement under translation and rotation, An architecture independent study of parallel segment trees, A framework and algorithms for circular drawings of graphs, Optimal shooting: Characterizations and applications, Lower bounds on algebraic random access machines, Pre-triangulations and liftable complexes, Minimization of decision trees is hard to approximate, Adaptive sampling for geometric problems over data streams, Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract], Kolmogorov Complexity Theory over the Reals, Translating a convex polygon to contain a maximum number of points., The Erdős--Nagy theorem and its ramifications, Proximity problems on line segments spanned by points, Approximate range searching using binary space partitions, A boundary element method for steady convective heat diffusion in three dimensions, Skeletonization based on error reduction, Cut loci in lens manifolds, Geometric Aspects of the Space of Triangulations, Spanning trees with low crossing number, Exact, efficient, and complete arrangement computation for cubic curves, Accuracy and efficiency of higher-order boundary element methods for steady convective heat diffusion in three-dimensions, Modélisation géométrique de la faisabilité de plusieurs mélanges, Searching on a line: a complete characterization of the optimal solution, Dynamic interpolation search revisited, Fast high-dimensional node generation with variable density, The geometry of conservative programs, Dual‐tree fast exact max‐kernel search, On the shortest separating cycle, Viscous fingering of miscible annular ring, On covering bounded sets by collections of circles of various radii, Local cohomology and stratification, Entropy solution at concave corners and ridges, and volume boundary layer tangential adaptivity, Two approaches to building time-windowed geometric data structures, On some matching problems under the color-spanning model, Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time, Rectilinear paths among rectilinear obstacles, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Chaining algorithms for multiple genome comparison, On farthest Voronoi cells, \(L_1\) geodesic farthest neighbors in a simple polygon and related problems, On digital plane preimage structure, An exact and efficient approach for computing a cell in an arrangement of quadrics, Digital plane preimage structure, Exact Image Reconstruction from a Single Projection through Real Computation, On paths in search or decision trees which require almost worst-case time, BAR-CODES OF SIERPIŃSKI RELATIVES WITH TRIANGLE CONVEX HULLS, Distribution-sensitive algorithms, The -Delaunay tessellation: Description of the model and geometry of typical cells, A linear-time heuristic for minimum rectangular coverings (Extended abstract), Translating polygons with applications to hidden surface removal, The visibility diagram: A data structure for visibility problems and motion planning, Space-sweep algorithms for parametric optimization, Improvements on geometric pattern matching problems, Voronoi diagrams of moving points in higher dimensional spaces, New results on binary space partitions in the plane (extended abstract), A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon, The two-line center problem from a polar view: a new algorithm and data structure, Quadrangulations of planar sets, A linear-time construction of the relative neighborhood graph within a histogram, Routing with delays when storage is costly, The buffer tree: A new technique for optimal I/O-algorithms, Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep, On the complexity of graph embeddings, Generalized approximate algorithms for point set congruence, Gaussian random fields: with and without covariances, Concatenable segment trees, Lower bounds for the matrix chain ordering problem, A simplified technique for hidden-line elimination in terrains, A plane-sweep algorithm for finding a closest pair among convex planar objects, Enclosing many boxes by an optimal pair of boxes, New parallel algorithms for convex hull and triangulation in 3-dimensional space, Approximation algorithms for a genetic diagnostics problem, Cartographic line simplication and polygon CSG formulae in O(n log* n) time, A quantum search algorithm of two-dimensional convex hull, Straight-line drawings of 1-planar graphs, The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication, Improved bound for the Gerver-Ramsey collinearity problem, On one approach to the estimation of a triangular element degeneration in a triangulation, CONVEX HULLS OF SIERPIŃSKI RELATIVES, Geometric pattern matching in d-dimensional space, Topology optimization of light structures using the natural neighbour radial point interpolation method, Shape-faithful graph drawings, Intersection graphs of maximal sub-polygons of \(k\)-lizards, Dynamic convex hulls under window-sliding updates, Optimal Sensor Positioning; A Probability Perspective Study, On computing the initial data for modeling of radiation-induced effects in porous materials, Dynamic connectivity in disk graphs, Exact and heuristic solutions for the prize‐collecting geometric enclosure problem, Analysis of the weighted Tchebycheff weight set decomposition for multiobjective discrete optimization problems, Kernel-based construction operators for Boolean sum and ruled geometry, Unrealistic models for realistic computations: how idealisations help represent mathematical structures and found scientific computing, Point enclosure problem for homothetic polygons, Robust numerical integration of embedded solids described in boundary representation, Estimation of tetrahedron degeneration in a tetrahedral partition of three-dimensional space, Separating a polyhedron by one translation from a set of obstacles, A parallel algorithm for channel routing, Hardness Results for Structured Linear Systems, THREE CHARACTERIZATIONS OF STRICT COHERENCE ON INFINITE-VALUED EVENTS, An efficient parallel algorithm for shortest paths in planar layered digraphs, Geometric Streaming Algorithms with a Sorting Primitive, Dynamic Algorithms for Visibility Polygons in Simple Polygons, Maximum Rectilinear Convex Subsets, Solution Reconstruction on Unstructured Tetrahedral Meshes UsingP1-Conservative Interpolation, Computational Origami Construction as Constraint Solving and Rewriting, Two-variable linear programming in parallel, On approximate range counting and depth, On exclusion regions for optimal triangulations, Minimum convex partition of a constrained point set, How to Morph Planar Graph Drawings, Algorithms for the line-constrained disk coverage and related problems, Lower bounds for computing geometric spanners and approximate shortest paths, Dynamic partition trees, The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study, Approximation algorithms for maximum two-dimensional pattern matching, A unified scheme for detecting fundamental curves in binary edge images, An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model, Regular and non-regular point sets: Properties and reconstruction, Output-sensitive generation of the perspective view of isothetic parallelepipeds, Fast algorithms for greedy triangulation, Applications of a semi-dynamic convex hull algorithm, Upper envelope onion peeling, Unnamed Item, Evaluation of sphericity error from coordinate measurement data using computational geometric techniques, Gauss map computation for free-form surfaces, Two-variable linear programming in parallel, Maintaining the extent of a moving point set, Conformal mapping in linear time, Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem, Distance Transformation on Two-Dimensional Irregular Isothetic Grids, Gift-Wrapping Based Preimage Computation Algorithm, Distributed distance-\(r\) covering problems on sparse high-girth graphs, Dynamic planar point location with optimal query time, Nearly optimal computations with structured matrices, Chebyshev centres, Jung constants, and their applications, On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic, Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle, Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model, On range searching with semialgebraic sets, Unnamed Item, Unnamed Item, K-Dominance in Multidimensional Data: Theory and Applications, Deletion in Abstract Voronoi Diagrams in Expected Linear Time., Unnamed Item, Numerical Approximation of the Value of a Stochastic Differential Game with Asymmetric Information, Dominance Product and High-Dimensional Closest Pair under L_infty