An Expander-Based Approach to Geometric Optimization
From MaRDI portal
Publication:4376177
DOI10.1137/S0097539794268649zbMath0888.68116OpenAlexW1985655539MaRDI QIDQ4376177
Publication date: 10 February 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794268649
facility locationcomputational geometryrange searchinggeometric optimizationslope selectionexpander graphsparametric searchingparametric-searching technique
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Discrete location and assignment (90B80) Discrete geometry (52C99) Graph theory (05C99)
Related Items
Reverse shortest path problem for unit-disk graphs, Covering many or few points with unit disks, Constrained square-center problems, Reverse shortest path problem in weighted unit-disk graphs, An efficient algorithm for the proximity connected two center problem, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, On reverse shortest paths in geometric proximity graphs, BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES, The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition, Covering point sets with two disjoint disks or squares, Proximity problems on line segments spanned by points, ALMOST OPTIMAL SOLUTIONS TO k-CLUSTERING PROBLEMS, ON ENUMERATING AND SELECTING DISTANCES, On regular vertices of the union of planar convex objects, COVERING A POINT SET BY TWO DISJOINT RECTANGLES, Shortest paths in intersection graphs of unit disks, On the planar two-center problem and circular hulls, COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET