scientific article; zbMATH DE number 1433426

Marc J. van Kreveld, Otfried Schwarzkopf, Mark T. de Berg, Mark H. Overmars

Publication date: 18 April 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

motion planning visibility computational geometry Delaunay triangulation Voronoi diagrams convex hulls arrangement of lines geometric searching polygon partitioning

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

An FPTAS for the parametric knapsack problem ⋮ Integral points in rational polygons: a numerical semigroup approach ⋮ Top-$k$ term-proximity in succinct space ⋮ On the arrangement of stochastic lines in $\mathbb{R}^2$ ⋮ Approximation algorithms for aligning points ⋮ On the computational complexity of 2-interval pattern matching problems ⋮ Approximating geometric bottleneck shortest paths ⋮ Advanced programming techniques applied to CGAL's arrangement package ⋮ Rotation and lighting invariant template matching ⋮ Adaptive finite difference methods for nonlinear elliptic and parabolic partial differential equations with free boundaries ⋮ Multiple point evaluation on combined tensor product supports ⋮ Visualization of road geometries based on CADD design standards ⋮ Fuzzy distance-based range queries over uncertain moving objects ⋮ Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems ⋮ A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums ⋮ On incremental rendering of silhouette maps of a polyhedral scene ⋮ Minimum weight pseudo-triangulations ⋮ Transforming pseudo-triangulations ⋮ A symmetry based multiobjective clustering technique for automatic evolution of clusters ⋮ Prophet: a context-aware location privacy-preserving scheme in location sharing service ⋮ The typical cell of a Voronoi tessellation on the sphere ⋮ Nearest-neighbor searching under uncertainty. I ⋮ The pairwise flowtime network construction problem ⋮ A hybrid inference system for improved curvature estimation in the level-set method using machine learning ⋮ Faster compression of patterns to rectangle rule lists ⋮ Mind the gap! ⋮ Error-correcting neural networks for two-dimensional curvature computation in the level-set method ⋮ Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints ⋮ Energy minimizing mountain ascent ⋮ I/O efficient dynamic data structures for longest prefix queries ⋮ Source-location privacy full protection in wireless sensor networks ⋮ A mathematical framework for modeling axon guidance ⋮ A computational learning theory of active object recognition under uncertainty ⋮ Biased range trees ⋮ An $O(n+m)$ certifying triconnnectivity algorithm for Hamiltonian graphs ⋮ Fast neighbor search by using revised $k$-d tree ⋮ Computing homotopic shortest paths efficiently ⋮ Algorithms for optimal area triangulations of a convex polygon ⋮ A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem ⋮ Dynamic 3-sided planar range queries with expected doubly-logarithmic time ⋮ GeoQuorums: implementing atomic memory in mobile ad hoc networks ⋮ Comparison of mixed and isoparametric boundary elements in time domain poroelasticity ⋮ INSIM-FT in three-dimensions with gravity ⋮ A particle-based free surface detection method and its application to the surface tension effects simulation in smoothed particle hydrodynamics (SPH) ⋮ A note on minimum-sum coverage by aligned disks ⋮ On reporting the $L_1$ metric closest pair in a query rectangle ⋮ Largest triangle inside a terrain ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ The generic Gröbner walk ⋮ Higher order mobile coverage control with applications to clustering of discrete sets ⋮ A tight lower bound for computing the diameter of a 3D convex polytope ⋮ Zone theorem for arrangements in dimension three ⋮ On local transformations in plane geometric graphs embedded on small grids ⋮ Query point visibility computation in polygons with holes ⋮ Lower bounds for expected-case planar point location ⋮ Planar multi-patch domain parameterization for isogeometric analysis based on evolution of fat skeleton ⋮ An optimal algorithm for the minimum disc cover problem ⋮ Finding the optimal shape of the leading-and-trailing car of a high-speed train using design-by-morphing ⋮ A bio-inspired B-spline offset feature for structural topology optimization ⋮ Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments ⋮ Adaptive sampling for geometric problems over data streams ⋮ Data structures for halfplane proximity queries and incremental Voronoi diagrams ⋮ Improved approximation bounds for planar point pattern matching ⋮ Location of weighted anti-ordered median straight lines with Euclidean distances ⋮ Improved output-sensitive snap rounding ⋮ Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in $d$-dimensions ⋮ Sweep synchronization as a global propagation mechanism ⋮ Aggregation for the probabilistic traveling salesman problem ⋮ A variational meshfree method for solving time-discrete diffusion equations ⋮ How to determine the minimum number of fuzzy rules to achieve given accuracy: a computational geometric approach to SISO case ⋮ A sweep-line algorithm for the inclusion hierarchy among circles ⋮ Approximate range searching: The absolute model ⋮ Planar graphs, negative weight edges, shortest paths, and near linear time ⋮ Fast multiscale clustering and manifold identification ⋮ Regression based automatic face annotation for deformable model building ⋮ Parallelization alternatives and their performance for the convex hull problem ⋮ Kinetic collision detection for balls ⋮ A numerical study into element type and mesh resolution for crystal plasticity finite element modeling of explicit grain structures ⋮ QuickhullDisk: a faster convex hull algorithm for disks ⋮ Distributed combinatorial maps for parallel mesh processing ⋮ Total least squares fitting of $k$-spheres in $n$-D Euclidean space using an $(n+2)$-D isometric representation ⋮ Enhancing point symmetry-based distance for data clustering ⋮ A hierarchical curve-based approach to the analysis of manifold data ⋮ Leveraging access mode declarations in a model for memory consistency in heterogeneous systems ⋮ Calculating the vertex unknowns of nine point scheme on quadrilateral meshes for diffusion equation ⋮ Equidistant representations: connecting coverage and uniformity in discrete biobjective optimization ⋮ Empirical geodesic graphs and CAT$(k)$ metrics for data analysis ⋮ A mortar method based on NURBS for curved interfaces ⋮ Dual weighted residual error estimation for the finite cell method ⋮ A non-iterative algorithm for generalized pig games ⋮ An elementary algorithm for digital arc segmentation ⋮ Computing large planar regions in terrains, with an application to fracture surfaces ⋮ The most points connected-covering problem with two disks ⋮ Crossing patterns of semi-algebraic sets ⋮ Error-correcting neural networks for semi-Lagrangian advection in the level-set method ⋮ Acrophobic guard watchtower problem ⋮ Multi-affine visible height correlation analysis for revealing rich structures of fractal time series ⋮ Synchronized sweep algorithms for scalable scheduling constraints ⋮ A numerical algorithm for multidimensional modeling of scattered data points ⋮ Isoperimetric enclosures ⋮ Computing the Smallest T-Shaped Polygon Containing k Points ⋮ BAR-CODES OF SIERPIŃSKI RELATIVES WITH TRIANGLE CONVEX HULLS ⋮ Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ The two‐median problem on Manhattan meshes ⋮ Semi-dynamic Connectivity in the Plane ⋮ Approximating Nearest Neighbor Distances ⋮ Efficient Time Integration of Maxwell's Equations with Generalized Finite Differences ⋮ The Offset Filtration of Convex Objects ⋮ Multiobjective Optimization via Parametric Optimization: Models, Algorithms, and Applications ⋮ Data structures for maintaining set partitions ⋮ Optimal Embedding into Star Metrics ⋮ Online Square Packing ⋮ Streaming Embeddings with Slack ⋮ Computation of Stackelberg Equilibria of Finite Sequential Games ⋮ Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning ⋮ Monte-Carlo Valuation of American Options: Facts and New Algorithms to Improve Existing Methods ⋮ Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties ⋮ How Superadditive Can a Risk Measure Be? ⋮ On farthest Bregman Voronoi cells ⋮ Space–Query-Time Tradeoff for Computing the Visibility Polygon ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ Geometry Helps to Compare Persistence Diagrams ⋮ Mixed Map Labeling ⋮ Continuous-Time Moving Network Voronoi Diagram ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Simulating curvilinear crack propagation in two dimensions with universal meshes ⋮ Rectangular partitions of a rectilinear polygon ⋮ On the parameterized complexity of the Maximum Exposure Problem ⋮ CONVEX HULLS OF SIERPIŃSKI RELATIVES ⋮ Two-Dimensional Pattern Matching with Combined Scaling and Rotation ⋮ Versioning Tree Structures by Path-Merging ⋮ Machine learning algorithms for three-dimensional mean-curvature computation in the level-set method ⋮ Simplified Planar Coresets for Data Streams ⋮ Boundary Labeling with Octilinear Leaders ⋮ Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem ⋮ A Unified Approach for the $H_\infty$-Stability Analysis of Classical and Fractional Neutral Systems with Commensurate Delays ⋮ Analysis of Highly Accurate Finite Element Based Algorithms for Computing Distances to Level Sets ⋮ Querying Relational Event Graphs Using Colored Range Searching Data Structures ⋮ Plastic Collapse Analysis of Mindlin–Reissner Plates Using a Stabilized Mesh-Free Method ⋮ How to Extend Visibility Polygons by Mirrors to Cover Invisible Segments ⋮ Transition scale-spaces: A computational theory for the discretized entorhinal cortex ⋮ Obstacle Numbers of Planar Graphs ⋮ I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ⋮ Optimal Triangulation with Steiner Points ⋮ Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations ⋮ Minkowski tensors of anisotropic spatial structure ⋮ How to Block Blood Flow by Using Elastic Coil ⋮ Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures ⋮ Statistical topology of perturbed two-dimensional lattices ⋮ Efficient and Qualified Mesh Generation for Gaussian Molecular Surface Using Adaptive Partition and Piecewise Polynomial Approximation ⋮ Markov incremental constructions ⋮ Workspace-Based Connectivity Oracle: An Adaptive Sampling Strategy for PRM Planning ⋮ Challenges and Advances in A Priori Routing ⋮ Analytic Evaluation of Collocation Integrals for the Radiosity Equation ⋮ Separable Distance Transformation and Its Applications ⋮ On Quality Indicators for Black-Box Level Set Approximation ⋮ On the number of regular vertices of the union of Jordan regions ⋮ Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract] ⋮ Multi-outlet retail site location assessment ⋮ An Elementary Algorithm for Digital Arc Segmentation ⋮ On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane ⋮ How to Morph Planar Graph Drawings ⋮ Stratifying High-Dimensional Data Based on Proximity to the Convex Hull Boundary ⋮ Access Control Encryption for Equality, Comparison, and More ⋮ Discontinuous Galerkin framework for adaptive solution of parabolic problems ⋮ Solving the Direction Field for Discrete Agent Motion ⋮ Unnamed Item ⋮ A nonconforming Crouzeix-Raviart type finite element on polygonal meshes ⋮ Graphs with Large Obstacle Numbers ⋮ On planar intersection graphs with forbidden subgraphs ⋮ Maximum Neighbour Voronoi Games ⋮ Generating All Triangulations of Plane Graphs (Extended Abstract) ⋮ Lagrangian and moving mesh methods for the convection diffusion equation ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ Model Predictive Control – Numerical Methods for the Invariant Sets Approximation ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Gift-Wrapping Based Preimage Computation Algorithm ⋮ Improved stretch factor of Delaunay triangulations of points in convex position ⋮ Unnamed Item ⋮ Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point ⋮ Range-Aggregate Queries Involving Geometric Aggregation Operations ⋮ On the Discrete Unit Disk Cover Problem ⋮ Critical Points of the Electric Field from a Collection of Point Charges ⋮ Inferring Obstacles and Path Validity from Visibility-Constrained Demonstrations ⋮ VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE ⋮ Computing a Minimum-Width Square or Rectangular Annulus with Outliers ⋮ Minimizing Sum of Truncated Convex Functions and Its Applications ⋮ Estimating monotone convex functions via sequential shape modification ⋮ Factorization of cp-rank-3 completely positive matrices ⋮ Compensated Convexity Methods for Approximations and Interpolations of Sampled Functions in Euclidean Spaces: Applications to Contour Lines, Sparse Data, and Inpainting ⋮ Efficient Lattice Width Computation in Arbitrary Dimension ⋮ A Novel Algorithm for Distance Transformation on Irregular Isothetic Grids ⋮ Analytical solutions of optimal portfolio rebalancing ⋮ Target-oriented Petri Net Synthesis ⋮ A Deep Learning Approach for the Computation of Curvature in the Level-Set Method ⋮ New Bounds for Range Closest-Pair Problems ⋮ Deletion in Abstract Voronoi Diagrams in Expected Linear Time. ⋮ Optimizing Query Perturbations to Enhance Shape Retrieval ⋮ Counting visible levels in bargraphs and set partitions ⋮ On Some Proximity Problems of Colored Sets ⋮ A meshfree large-deformation analysis method for geotechnical engineering based on the RBF field variable mapping technology ⋮ The Earth is nearly flat: Precise and approximate algorithms for detecting vulnerable regions of networks in the plane and on the sphere ⋮ Shadows of Newton polytopes ⋮ Simplifying obstacles for Steiner network problems in the plane ⋮ Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms ⋮ Modeling combinatorial disjunctive constraints via junction trees ⋮ Network augmentation for disaster‐resilience against geographically correlated failure ⋮ Capacity provisioning for evacuation on path networks ⋮ Path planning in a weighted planar subdivision under the Manhattan metric ⋮ Unnamed Item ⋮ Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints ⋮ Drawing graphs as spanners ⋮ On the separability of stochastic geometric objects, with applications ⋮ On length measures of planar closed curves and the comparison of convex shapes ⋮ Computing a minimum-width square or rectangular annulus with outliers ⋮ Computing minimum-area rectilinear convex hull and $L$-shape ⋮ Gift-wrapping based preimage computation algorithm ⋮ Linear data structures for fast ray-shooting amidst convex polyhedra ⋮ Optimal bounding cones of vectors in three dimensions ⋮ Covering many or few points with unit disks ⋮ The maximum number of faces of the Minkowski sum of two convex polytopes ⋮ Delaunay triangulations of closed Euclidean $d$-orbifolds ⋮ Guarding galleries and terrains ⋮ Straight skeletons and mitered offsets of nonconvex polytopes ⋮ The phase flow method ⋮ Bayesian spatial modelling of gamma ray count data ⋮ A new representation of orientable 2-manifold polygonal surfaces for geometric modelling ⋮ Computing the conjugate of convex piecewise linear-quadratic bivariate functions ⋮ The visibility-Voronoi complex and its applications ⋮ A consensus problem for a class of vehicles with 2-D dynamics ⋮ Geometric dilation of closed planar curves: New lower bounds ⋮ Sequential dependency computation via geometric data structures ⋮ Improved algorithms for the farthest colored Voronoi diagram of segments ⋮ On the central path problem ⋮ Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis ⋮ Incremental Voronoi diagrams ⋮ Mining spatial colocation patterns: a different framework ⋮ Faster $p$-adic feasibility for certain multivariate sparse polynomials ⋮ Arrangements on parametric surfaces. II: Concretizations and applications ⋮ A sparse octree gravitational $N$-body code that runs entirely on the GPU processor ⋮ Casting a polyhedron with directional uncertainty ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Pachinko ⋮ Point-set embeddings of plane $3$-trees ⋮ A faster circle-sweep Delaunay triangulation algorithm ⋮ Mutual exclusion in MANETs using quorum agreements ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ On bounded leg shortest paths problems ⋮ The stochastic walk algorithms for point location in pseudo-triangulations ⋮ Optimal selection of local approximants in RBF-PU interpolation ⋮ Weak equilibrium in a spatial model ⋮ Decomposable algorithms for nearest neighbor computing ⋮ Computing efficiently the lattice width in any dimension ⋮ Energy-efficient paths in radio networks ⋮ Minimizing the diameter of a spanning tree for imprecise points ⋮ Spherical fast multiscale approximation by locally compact orthogonal wavelets ⋮ The weighted farthest color Voronoi diagram on trees and graphs. ⋮ Guarding curvilinear art galleries with vertex or point guards ⋮ Living on the moon: topological optimization of a 3D-printed lunar shelter ⋮ The $k$-centrum straight-line location problem ⋮ Maximizing Voronoi regions of a set of points enclosed in a circle with applications to facility location ⋮ Cutting a convex polyhedron out of a sphere ⋮ On the structure of graphs with low obstacle number ⋮ A note on the complexity of real algebraic hypersurfaces ⋮ Data structures for extension violations in a query range ⋮ Spiderman graph: visibility in urban regions ⋮ Blaschke-type theorem and separation of disjoint closed geodesic convex sets ⋮ An algorithm for continuous piecewise linear bounding of discrete time series data ⋮ Scalable continuous object detection and tracking in sensor networks ⋮ Improved bounds on the union complexity of fat objects ⋮ Approximation schemes for the parametric knapsack problem ⋮ Adaptive spacetime meshing for discontinuous Galerkin methods ⋮ Accelerating smooth molecular surface calculation ⋮ Recursive learning for sparse Markov models ⋮ Interval scheduling maximizing minimum coverage ⋮ Estimation of graphical models whose conditional independence graphs are interval graphs and its application to modelling linkage disequilibrium ⋮ Capturing crossings: convex hulls of segment and plane intersections ⋮ Towards optimal range medians ⋮ Boundary labeling with octilinear leaders ⋮ Approximation algorithms for shortest descending paths in terrains ⋮ Minimum weight convex Steiner partitions ⋮ Orthogonal segment stabbing ⋮ The relative neighbourhood graph is a part of every $30^\circ $-triangulation ⋮ Time-optimal coordination of flexible manufacturing systems using deterministic finite automata and mixed integer linear programming ⋮ Cooperative TSP ⋮ Complexity of token swapping and its variants ⋮ Spline-based reservoir's geometry reconstruction and mesh generation for coupled flow and mechanics simulation ⋮ Fast distance transformation on irregular two-dimensional grids ⋮ Partial-matching RMS distance under translation: combinatorics and algorithms ⋮ GAPS: A clustering method using a new point symmetry-based distance measure ⋮ Sign-preserving of principal eigenfunctions in P1 finite element approximation of eigenvalue problems of second-order elliptic operators ⋮ Parallelized event chain algorithm for dense hard sphere and polymer systems ⋮ A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters ⋮ On the minimum total length of interval systems expressing all intervals, and range-restricted queries ⋮ Measure of circularity for parts of digital boundaries and its fast computation ⋮ Translational packing of arbitrary polytopes ⋮ Multiscale cell-based coarsening for discontinuous problems ⋮ The cyclical scheduling problem ⋮ Kinetic collision detection for convex fat objects ⋮ A practical approximation algorithm for the LMS line estimator ⋮ Shortest descending paths through given faces ⋮ Efficiency for continuous facility location problems with attraction and repulsion ⋮ Computing the update of the repeated median regression line in linear time ⋮ Clamshell casting ⋮ Practical multiagent rendezvous through modified circumcenter algorithms ⋮ A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation ⋮ Anisotropic mesh quality measures and adaptation for polygonal meshes ⋮ Heuristics for container loading of furniture ⋮ Robustness of $k$-gon Voronoi diagram construction ⋮ Minimum-width double-strip and parallelogram annulus ⋮ Approximation algorithms for terrain guarding. ⋮ Depth-optimized convexity cuts