An Expander-Based Approach to Geometric Optimization

DOI10.1137/S0097539794268649zbMath0888.68116OpenAlexW1985655539MaRDI QIDQ4376177

Matthew J. Katz, Micha Sharir

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

zbMATH Keywords

facility locationcomputational geometryrange searchinggeometric optimizationslope selectionexpander graphsparametric searchingparametric-searching technique

Mathematics Subject Classification ID

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