License: 
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.2020.50
URN: urn:nbn:de:0030-drops-122088
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12208/
Har-Peled, Sariel ;
Jones, Mitchell
Fast Algorithms for Geometric Consensuses
Abstract
Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P.
We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others.
BibTeX - Entry
@InProceedings{harpeled_et_al:LIPIcs:2020:12208,
author = {Sariel Har-Peled and Mitchell Jones},
title = {{Fast Algorithms for Geometric Consensuses}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {50:1--50:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12208},
URN = {urn:nbn:de:0030-drops-122088},
doi = {10.4230/LIPIcs.SoCG.2020.50},
annote = {Keywords: Geometric optimization, centerpoint, voting games}
}
|
Keywords: |
|
Geometric optimization, centerpoint, voting games |
|
Collection: |
|
36th International Symposium on Computational Geometry (SoCG 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
08.06.2020 |
