Relative convex hulls in semi-dynamic arrangements
From MaRDI portal
Publication:476434
DOI10.1007/s00453-012-9679-6zbMath1317.68250OpenAlexW1964492068MaRDI QIDQ476434
Csaba D. Tóth, Mashhood Ishaque
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9679-6
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
Shortest paths and convex hulls in 2D complexes with non-positive curvature ⋮ Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon ⋮ Vertex-colored encompassing graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arrangements on parametric surfaces. I: General framework and infrastructure
- Geodesic ham-sandwich cuts
- Tight bounds for connecting sites across barriers
- Topological sweep of the complete graph
- Refolding planar polygons
- Topologically sweeping an arrangement
- Maintenance of configurations in the plane
- Applications of a semi-dynamic convex hull algorithm
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Ray shooting in polygons using geodesic triangulations
- Segment endpoint visibility graphs are Hamiltonian
- Straightening polygonal arcs and convexifying polygonal cycles
- Kinetic collision detection between two simple polygons.
- Morphing simple polygons
- Optimal shortest path queries in a simple polygon
- On separating two simple polygons by a single translation
- Dynamic planar convex hull operations in near-logarithmic amortized time
- Algorithms for Reporting and Counting Geometric Intersections
- Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
- Geodesic Fréchet distance inside a simple polygon
- Euclidean shortest paths in the presence of rectilinear barriers
- On the convex layers of a planar set
- An optimal real-time algorithm for planar convex hulls
- Approximate Euclidean Shortest Paths in 3-Space
- Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons
- GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON
- A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps
- Shooting permanent rays among disjoint polygons in the plane
- Visibility Algorithms in the Plane
- Minimum-Perimeter Polygons of Digitized Silhouettes
- Acute triangulations of polygons
- Algorithms - ESA 2003
- Sweeps, arrangements and signotopes
- Locked and unlocked chains of planar shapes
This page was built for publication: Relative convex hulls in semi-dynamic arrangements