Some dynamic computational geometry problems

DOI10.1016/0898-1221(85)90105-1zbMath0586.68085OpenAlexW2039879619WikidataQ56558215 ScholiaQ56558215MaRDI QIDQ1071526

Publication date: 1985

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(85)90105-1

zbMATH Keywords

convex hull moving points

Mathematics Subject Classification ID

Computing methodologies and applications (68U99)

Related Items

The Minimum Moving Spanning Tree Problem, ``The big sweep: On the power of the wavefront approach to Voronoi diagrams, The minimum moving spanning tree problem, Kinetic clustering of points on the line, On minimum and maximum spanning trees of linearly moving points, Parametric problems on graphs of bounded tree-width, Voronoi diagrams of moving points in higher dimensional spaces, Separating translates in the plane: Combinatorial bounds and an algorithm, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, On the two-dimensional Davenport-Schinzel problem, Orthogonal queries in segments, Trajectory clustering of points in \(\mathbb{R}\), An algorithm for generalized point location and its applications, Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean \(d\)-dimensional space, PROBABILISTIC ANALYSIS FOR DISCRETE ATTRIBUTES OF MOVING POINTS, The overlay of lower envelopes and its applications, Fast algorithms for collision and proximity problems involving moving geometric objects, “The big sweep”: On the power of the wavefront approach to Voronoi diagrams, Common intersections of polygons, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions, CONTINUOUS PATH VERIFICATION IN MULTI-AXIS NC-MACHINING, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, On \(k\)-sets in arrangements of curves and surfaces, A sensor-based framework for kinetic data compression, Linear approximation of simple objects, Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, A convex polygon among polygonal obstacle: Placement and high-clearance motion, Transitions in geometric minimum spanning trees, Distribution-sensitive construction of the greedy spanner, The upper envelope of Voronoi surfaces and its applications, Dynamic computational geometry on meshes and hypercubes, Approximation algorithm for the kinetic robust \(k\)-center problem, Finding the upper envelope of n line segments in O(n log n) time, The maximum absolute deviation measure in location problems on networks, Fréchet distance between a line and avatar point set, Algorithms for covering multiple barriers, On Kinetic Delaunay Triangulations, Maintaining the extent of a moving point set, QuickhullDisk: a faster convex hull algorithm for disks, On the general motion-planning problem with two degrees of freedom, On arrangements of Jordan arcs with three intersections per pair, The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2, An algorithmic toolbox for network calculus, A nearly optimal deterministic parallel Voronoi diagram algorithm, Energy-optimal routes for battery electric vehicles, Swap conditions for dynamic Voronoi diagrams for circles and line segments, Ready, set, go! The Voronoi diagram of moving points that start from a line, Complexity of projected images of convex subdivisions, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, Structural tolerance and Delaunay triangulation, Voronoi Diagrams of Moving Points, Some dynamic computational geometry problems, Visibility with a moving point of view

Cites Work