An Expander-Based Approach to Geometric Optimization

DOI10.1137/S0097539794268649MaRDI QIDQ4376177zbMATH OpenOpenAlexFDO

Authors 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

computational geometryrange searchingfacility locationgeometric optimizationexpander graphsslope selectionparametric 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) Graph theory (05C99) Discrete geometry (52C99) Discrete location and assignment (90B80)

Recommendations

• Optimal slope selection via expanders
• On nonlinear parametric search
• On some geometric selection and optimization problems via sorted matrices
• scientific article; zbMATH DE number 742950
• Applications of Parametric Searching in Geometric Optimization

Cited in

(31)

• Improved algorithms for distance selection and related problems
• Reverse shortest path problem for unit-disk graphs
• Covering many or few points with unit disks
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Covering point sets with two disjoint disks or squares
• Shortest paths in intersection graphs of unit disks
• A general technique for searching in implicit sets via function inversion
• Constrained square-center problems
• On regular vertices of the union of planar convex objects
• Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
• Optimal algorithm for the planar two-center problem
• Reverse shortest path problem in weighted unit-disk graphs
• Almost optimal solutions to k-clustering problems
• Proximity problems on line segments spanned by points
• On some geometric selection and optimization problems via sorted matrices
• Computing the minimum bottleneck moving spanning tree
• An efficient algorithm for the proximity connected two center problem
• Covering a point set by two disjoint rectangles
• On reverse shortest paths in geometric proximity graphs
• Optimal algorithm for the planar two-center problem
• Geometric matching and bottleneck problems
• Semi-algebraic off-line range searching and biclique partitions in the plane
• COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET
• Constrained two-line center problems
• On two simple[st] learning tasks
• An optimal and practical algorithm for the planar 2-center problem
• Optimal slope selection via expanders
• BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES
• On the planar two-center problem and circular hulls
• ON ENUMERATING AND SELECTING DISTANCES
• The Euclidean bottleneck Steiner path problem and other applications of ( , )-pair decomposition

This page was built for publication: An Expander-Based Approach to Geometric Optimization

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