@article{46cc5108082044648beb10ebb6cdc2c2,
title = "OPTIMAL ALGORITHMS FOR GEOMETRIC CENTERS AND DEPTH",
abstract = "We develop a general randomized technique for solving implicit linear programming problems, where the collection of constraints are defined implicitly by an underlying ground set of elements. In many cases, the structure of the implicitly defined constraints can be used to obtain faster linear program solvers. We apply this technique to obtain near-optimal algorithms for a variety of fundamental problems in geometry. For a given point set P of size n in Rd, we develop algorithms for computing geometric centers of a point set, including the centerpoint and the Tukey median, and several other more involved measures of centrality. For d = 2, the new algorithms run in O(n log n) expected time, which is optimal, and for higher constant d > 2, the expected time bound is within one logarithmic factor of O(nd 1), which is also likely near optimal for some of the problems.",
keywords = "centerpoint, depth, linear programming",
author = "Chan, {Timothy M.} and Sariel Har-Peled and Mitchell Jones",
note = "Funding Information: \ast Received by the editors May 27, 2021; accepted for publication (in revised form) December 22, 2021; published electronically May 19, 2022. This paper is a merge of two conference papers that were published 16 years apart. The first paper [14] appeared in SODA 2004, and the second paper [40] (which can be viewed as an applications paper of the first paper) appeared in SoCG 2020. https://doi.org/10.1137/21M1423324 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : The work of the first author was partially supported by NSF award CCF-1814026. The work of the second and third authors was supported by AF awards CCF-1421231 and CCF-1907400. The work of Qing Cheng and Jie Shen is partially supported by NSF (National Science Foundation), USA Grant DMS-2012585 and AFOSR (Air Force Office of Scientific Research), USA Grant FA9550-20-1-0309. Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics Publications. All rights reserved.",
year = "2022",
doi = "10.1137/21M1423324",
language = "English (US)",
volume = "51",
pages = "627--663",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",
}