# Bipartite diameter and other measures under translation

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

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

## תקציר

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

שפה מקורית אנגלית 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 Rolf Niedermeier, Christophe Paul Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing 9783959771009 https://doi.org/10.4230/LIPIcs.STACS.2019.8 פורסם - 1 מרץ 2019 כן 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 - Berlin, גרמניהמשך הזמן: 13 מרץ 2019 → 16 מרץ 2019

### סדרות פרסומים

שם Leibniz International Proceedings in Informatics, LIPIcs 126 1868-8969

### כנס

כנס 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 גרמניה Berlin 13/03/19 → 16/03/19