@inproceedings{994e101a7647401cb13f2ad2328f7399,
title = "Fast algorithms for geometric consensuses",
abstract = "Let P be a set of n points in Rd 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(nd−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.",
keywords = "Centerpoint, Geometric optimization, Voting games",
author = "Sariel Har-Peled and Mitchell Jones",
note = "Funding Information: Funding Sariel Har-Peled: Supported in part by NSF AF award CCF-1907400. Mitchell Jones: Supported in part by NSF AF award CCF-1907400. Publisher Copyright: {\textcopyright} Sariel Har-Peled and Mitchell Jones; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020).; 36th International Symposium on Computational Geometry, SoCG 2020 ; Conference date: 23-06-2020 Through 26-06-2020",
year = "2020",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2020.50",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Sergio Cabello and Chen, {Danny Z.}",
booktitle = "36th International Symposium on Computational Geometry, SoCG 2020",
}