Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.28
URN: urn:nbn:de:0030-drops-87412
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8741/
David, Roee ; C. S., Karthik ; Laekhanukit, Bundit
On the Complexity of Closest Pair via Polar-Pair of Point-Sets
| pdf-format: |
|
Abstract
Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Delta is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact dimension of the complete bipartite graph K_{n,n} in various L^p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.
BibTeX - Entry
@InProceedings{david_et_al:LIPIcs:2018:8741,
author = {Roee David and Karthik C. S. and Bundit Laekhanukit},
title = {{On the Complexity of Closest Pair via Polar-Pair of Point-Sets}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {28:1--28:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8741},
URN = {urn:nbn:de:0030-drops-87412},
doi = {10.4230/LIPIcs.SoCG.2018.28},
annote = {Keywords: Contact dimension, Sphericity, Closest Pair, Fine-Grained Complexity}
}
| Keywords: | Contact dimension, Sphericity, Closest Pair, Fine-Grained Complexity | |
| Seminar: | 34th International Symposium on Computational Geometry (SoCG 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 08.06.2018 |
