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 geometryexpander graphsfacility locationgeometric optimizationparametric searchingparametric-searching techniquerange searchingslope selection

Mathematics Subject Classification ID

Graph theory (05C99) Discrete geometry (52C99) 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)

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

(39)

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

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)