Faster algorithms for growing prioritized disks and rectangles

DOI10.1016/j.comgeo.2019.02.001zbMath1456.68219OpenAlexW2608045512WikidataQ128363237 ScholiaQ128363237MaRDI QIDQ2330036

André van Renssen, Sang Won Bae, Eunjin Oh, Hee-Kap Ahn, Wolfgang Mulzer, Matias Korman, Antoine Vigneron, Jong Min Choi, Ji-won Park

Publication date: 18 October 2019

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8219/

zbMATH Keywords

quadtreecondition numberdata structureslower boundelimination order

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (1)

Agglomerative clustering of growing squares

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Ray shooting in polygons using geodesic triangulations
• Parametrized runtimes for label tournaments
• Crushing Disks Efficiently
• Almost tight upper bounds for vertical decompositions in four dimensions
• Efficient Point Location in a Convex Spatial Cell-Complex
• Computing Envelopes in Four Dimensions with Applications
• Growing Balls in ℝ^d
• Agglomerative clustering of growing squares

This page was built for publication: Faster algorithms for growing prioritized disks and rectangles