Some dynamic computational geometry problems

We consider some problems in computational geometry when every one of the input points is moving in a prescribed manner.

Cites work

A Combinatorial Problem Connected with Differential Equations
A combinatorial problem connected with differential equations II
A Lower Bound to Finding Convex Hulls
An efficient algorithm for determining the convex hull of a finite planar set
Convex hulls of finite sets of points in two and three dimensions
scientific article; zbMATH DE number 3557226 (Why is no real title available?)
scientific article; zbMATH DE number 3569833 (Why is no real title available?)
On a problem of Davenport and Schinzel
On Finding the Maxima of a Set of Vectors
On the (n n) lower bound for convex hull and maximal vector determination
On the complexity of computations under varying sets of primitives
Some dynamic computational geometry problems

Cited in

(63)

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

This page was built for publication: Some dynamic computational geometry problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071526)