Fast algorithms for geometric consensuses

Sariel Har-Peled, Mitchell Jones

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(nd1 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.

Original languageEnglish (US)
Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771436
DOIs
StatePublished - Jun 1 2020
Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
Duration: Jun 23 2020Jun 26 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume164
ISSN (Print)1868-8969

Conference

Conference36th International Symposium on Computational Geometry, SoCG 2020
CountrySwitzerland
CityZurich
Period6/23/206/26/20

Keywords

  • Centerpoint
  • Geometric optimization
  • Voting games

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Fast algorithms for geometric consensuses'. Together they form a unique fingerprint.

Cite this