Publication:4947407

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

Publication date: 18 April 2000

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

Mathematics Subject Classification ID

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

A consensus problem for a class of vehicles with 2-D dynamics, Orthogonal segment stabbing, A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters, Measure of circularity for parts of digital boundaries and its fast computation, Depth-optimized convexity cuts, 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, Guarding galleries and terrains, The phase flow method, Bayesian spatial modelling of gamma ray count data, A new representation of orientable 2-manifold polygonal surfaces for geometric modelling, The visibility-Voronoi complex and its applications, Geometric dilation of closed planar curves: New lower bounds, Guarding curvilinear art galleries with vertex or point guards, Improved bounds on the union complexity of fat objects, Adaptive spacetime meshing for discontinuous Galerkin methods, 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, Boundary labeling with octilinear leaders, Approximation algorithms for shortest descending paths in terrains, 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, Fast distance transformation on irregular two-dimensional grids, GAPS: A clustering method using a new point symmetry-based distance measure, On the minimum total length of interval systems expressing all intervals, and range-restricted queries, Translational packing of arbitrary polytopes, Multiscale cell-based coarsening for discontinuous problems, 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, Heuristics for container loading of furniture, Robustness of \(k\)-gon Voronoi diagram construction, Casting a polyhedron with directional uncertainty, The weighted farthest color Voronoi diagram on trees and graphs., Approximation algorithms for terrain guarding., How to determine the minimum number of fuzzy rules to achieve given accuracy: a computational geometric approach to SISO case, An elementary algorithm for digital arc segmentation, Computing large planar regions in terrains, with an application to fracture surfaces, Approximation algorithms for aligning points, On the computational complexity of 2-interval pattern matching problems, Approximating geometric bottleneck shortest paths, Comparison of mixed and isoparametric boundary elements in time domain poroelasticity, Approximate range searching: The absolute model, Advanced programming techniques applied to CGAL's arrangement package, Rotation and lighting invariant template matching, Visualization of road geometries based on CADD design standards, 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 mathematical framework for modeling axon guidance, 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, Extracting constrained 2-interval subsets in 2-interval sets, The generic Gröbner walk, A tight lower bound for computing the diameter of a 3D convex polytope, 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, An optimal algorithm for the minimum disc cover problem, Adaptive sampling for geometric problems over data streams, Improved approximation bounds for planar point pattern matching, Improved output-sensitive snap rounding, Sweep synchronization as a global propagation mechanism, Aggregation for the probabilistic traveling salesman problem, A variational meshfree method for solving time-discrete diffusion equations, A sweep-line algorithm for the inclusion hierarchy among circles, Planar graphs, negative weight edges, shortest paths, and near linear time, Fast multiscale clustering and manifold identification, Parallelization alternatives and their performance for the convex hull problem, Calculating the vertex unknowns of nine point scheme on quadrilateral meshes for diffusion equation, Crossing patterns of semi-algebraic sets, Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems, A symmetry based multiobjective clustering technique for automatic evolution of clusters, Graphs with Large Obstacle Numbers, Optimal Embedding into Star Metrics, Online Square Packing, Streaming Embeddings with Slack, The two‐median problem on Manhattan meshes, Two-Dimensional Pattern Matching with Combined Scaling and Rotation, Versioning Tree Structures by Path-Merging, Simplified Planar Coresets for Data Streams, Boundary Labeling with Octilinear Leaders, Workspace-Based Connectivity Oracle: An Adaptive Sampling Strategy for PRM Planning, Challenges and Advances in A Priori Routing, Discontinuous Galerkin framework for adaptive solution of parabolic problems, On planar intersection graphs with forbidden subgraphs, Maximum Neighbour Voronoi Games, Generating All Triangulations of Plane Graphs (Extended Abstract), Model Predictive Control – Numerical Methods for the Invariant Sets Approximation, Multi-outlet retail site location assessment, Computing the Smallest T-Shaped Polygon Containing k Points, Data structures for maintaining set partitions, Solving the Direction Field for Discrete Agent Motion, Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning, Space–Query-Time Tradeoff for Computing the Visibility Polygon, Processing an Offline Insertion-Query Sequence with Applications, 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, Lagrangian and moving mesh methods for the convection diffusion equation, Gift-Wrapping Based Preimage Computation Algorithm, VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE, Markov incremental constructions, Analytic Evaluation of Collocation Integrals for the Radiosity Equation, Critical Points of the Electric Field from a Collection of Point Charges, Estimating monotone convex functions via sequential shape modification, Efficient Lattice Width Computation in Arbitrary Dimension, A Novel Algorithm for Distance Transformation on Irregular Isothetic Grids