Aronov, Boris ;
Filtser, Omrit ;
Katz, Matthew J. ;
Sheikhan, Khadijeh
Bipartite Diameter and Other Measures Under Translation
Abstract
Let A and B be two sets of points in R^d, 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 in A, b in 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 in A, b in B}, and (iii) the union width in two and three dimensions, that is union_width(A,B) = width(A cup B). For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present nearlineartime algorithms in R^2 and R^3, for uniformity we describe a roughly O(n^{9/4})time algorithm, and for union width we offer a nearlineartime algorithm in R^2 and a quadratictime one in R^3.
BibTeX  Entry
@InProceedings{aronov_et_al:LIPIcs:2019:10247,
author = {Boris Aronov and Omrit Filtser and Matthew J. Katz and Khadijeh Sheikhan},
title = {{Bipartite Diameter and Other Measures Under Translation}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {8:18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10247},
doi = {10.4230/LIPIcs.STACS.2019.8},
annote = {Keywords: Translationinvariant similarity measures, Geometric optimization, Minimumwidth annulus}
}
2019
Keywords: 

Translationinvariant similarity measures, Geometric optimization, Minimumwidth annulus 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

2019 