Bipartite diameter and other measures under translation

DOI10.1007/s00454-022-00433-5OpenAlexW4294786647WikidataQ114229282 ScholiaQ114229282MaRDI QIDQ2172648

Matthew J. Katz, Boris Aronov, Omrit Filtser, Khadijeh Sheikhan

Publication date: 16 September 2022

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-022-00433-5

zbMATH Keywords

geometric optimizationminimum-width annulustranslation-invariant similarity measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing convolutions by reciprocal search
• The upper envelope of Voronoi surfaces and its applications
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Approximate decision algorithms for point set congruence
• Efficient randomized algorithms for some geometric optimization problems
• Congruence, similarity, and symmetries of geometric objects
• Applications of random sampling in computational geometry. II
• Approximate congruence in nearly linear time
• Maximum overlap and minimum convex hull of two convex polyhedra under translations
• Simple algorithms for partial point set pattern matching under rigid motion
• Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms
• Hausdorff distance under translation for points and balls
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Computing the width of a set
• Applications of Parametric Searching in Geometric Optimization
• Las Vegas algorithms for linear and integer programming when the dimension is small
• A combinatorial bound for linear programming and related problems
• Deterministic algorithms for 3-D diameter and some 2-D lower envelopes
• Computing Correlation between Piecewise-Linear Functions
• Geometry helps in bottleneck matching and related problems