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 higher 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 and a subquadratic algorithm in Rd for any fixed d≥ 4 , for uniformity we describe a roughly O(n9 / 4) -time algorithm in the plane, and for union width we offer a near-linear-time algorithm in R2 and a quadratic-time one in R3.

שפה מקוריתאנגלית
מספר המאמר3
עמודים (מ-עד)647-663
מספר עמודים17
כתב עתDiscrete and Computational Geometry
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוק׳ 2022

הערה ביבליוגרפית

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Bipartite Diameter and Other Measures Under Translation'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי