TY - GEN
T1 - Bipartite diameter and other measures under translation
AU - Aronov, Boris
AU - Filtser, Omrit
AU - Katz, Matthew J.
AU - Sheikhan, Khadijeh
N1 - Funding Information:
Boris Aronov: Work on this paper by Boris Aronov was supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by grant 2014/170 from the US-Israel Binational Science Foundation. Omrit Filtser: Work on this paper by Omrit Filtser was supported by the Israel Ministry of Science, Technology & Space, and by the Lynn and William Frankel Center. Matthew J. Katz: Work on this paper by Matthew Katz was supported by grant 1884/16 from the Israel Science Foundation, and by grant 2014/170 from the US-Israel Binational Science Foundation. Khadijeh Sheikhan: Work on this paper by Khadijeh Sheikhan was supported by NSF Grant CCF-12-18791.
Funding Information:
Funding Boris Aronov: Work on this paper by Boris Aronov was supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by grant 2014/170 from the US-Israel Binational Science Foundation. Omrit Filtser: Work on this paper by Omrit Filtser was supported by the Israel Ministry of Science, Technology & Space, and by the Lynn and William Frankel Center. Matthew J. Katz: Work on this paper by Matthew Katz was supported by grant 1884/16 from the Israel Science Foundation, and by grant 2014/170 from the US-Israel Binational Science Foundation. Khadijeh Sheikhan: Work on this paper by Khadijeh Sheikhan was supported by NSF Grant CCF-12-18791.
Publisher Copyright:
© Boris Aronov, Omrit Filtser, Matthew J. Katz, and Khadijeh Sheikhan.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - Let A and B be two sets of points in Rd, where |A| = |B| = n and the distance between them is defined by some bipartite measure dist(A, B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A, B) = max{d(a, b) | a ∈ A, b ∈ B}, where d(a, b) is the Euclidean distance between a and b, (ii) the uniformity in the plane, that is uni(A, B) = diam(A, B) − d(A, B), where d(A, B) = min{d(a, b) | a ∈ A, b ∈ B}, and (iii) the union width in two and three dimensions, that is union_width(A, B) = width(A ∪ B). For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present near-linear-time algorithms in R2 and R3, for uniformity we describe a roughly O(n9/4)-time algorithm, and for union width we offer a near-linear-time algorithm in R2 and a quadratic-time one in R3
AB - Let A and B be two sets of points in Rd, where |A| = |B| = n and the distance between them is defined by some bipartite measure dist(A, B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A, B) = max{d(a, b) | a ∈ A, b ∈ B}, where d(a, b) is the Euclidean distance between a and b, (ii) the uniformity in the plane, that is uni(A, B) = diam(A, B) − d(A, B), where d(A, B) = min{d(a, b) | a ∈ A, b ∈ B}, and (iii) the union width in two and three dimensions, that is union_width(A, B) = width(A ∪ B). For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present near-linear-time algorithms in R2 and R3, for uniformity we describe a roughly O(n9/4)-time algorithm, and for union width we offer a near-linear-time algorithm in R2 and a quadratic-time one in R3
KW - Geometric optimization
KW - Minimum-width annulus
KW - Translation-invariant similarity measures
UR - http://www.scopus.com/inward/record.url?scp=85074924983&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074924983&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2019.8
DO - 10.4230/LIPIcs.STACS.2019.8
M3 - Conference contribution
AN - SCOPUS:85074924983
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
A2 - Niedermeier, Rolf
A2 - Paul, Christophe
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
Y2 - 13 March 2019 through 16 March 2019
ER -