Centerpoint (geometry)

In statistics and computational geometry, the notion of centerpoint is a generalization of the median to data in higher-dimensional Euclidean space. Given a set of points in d-dimensional space, a centerpoint of the set is a point such that any hyperplane that goes through that point divides the set of points in two roughly equal subsets: the smaller part should have at least a 1/(d + 1) fraction of the points. Like the median, a centerpoint need not be one of the data points. Every non-empty set of points (with no duplicates) has at least one centerpoint.

Closely related concepts are the Tukey depth of a point (the minimum number of sample points on one side of a hyperplane through the point) and a Tukey median of a point set (a point maximizing the Tukey depth). A centerpoint is a point of depth at least n/(d + 1), and a Tukey median must be a centerpoint, but not every centerpoint is a Tukey median. Both terms are named after John Tukey.

For a different generalization of the median to higher dimensions, see geometric median.

Existence

A simple proof of the existence of a centerpoint may be obtained using Helly's theorem. Suppose there are n points, and consider the family of closed half-spaces that contain more than dn/(d + 1) of the points. Fewer than n/(d + 1) points are excluded from any one of these halfspaces, so the intersection of any subset of d + 1 of these halfspaces must be nonempty. By Helly's theorem, it follows that the intersection of all of these halfspaces must also be nonempty. Any point in this intersection is necessarily a centerpoint.

Algorithms

For points in the Euclidean plane, a centerpoint may be constructed in linear time.[1] In any dimension d, a Tukey median (and therefore also a centerpoint) may be constructed in time O(nd − 1 + n log n).[2]

A randomized algorithm that repeatedly replaces sets of d + 2 points by their Radon point can be used to compute an approximation to a centerpoint of any point set, in the sense that its Tukey depth is linear in the sample set size, in an amount of time that is polynomial in the dimension.[3][4]

References

Citations

  1. ^ Jadhav & Mukhopadhyay (1994).
  2. ^ Chan (2004).
  3. ^ Clarkson et al. (1996).
  4. ^ Har-Peled & Jones (2020)

Sources

  • Chan, Timothy M. (2004), "An optimal randomized algorithm for maximum Tukey depth", Proc. 15th ACM–SIAM Symp. on Discrete Algorithms (SODA 2004), Society for Industrial and Applied Mathematics, pp. 430–436, ISBN 978-0-89871-558-3.
  • Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (September 1996), "Approximating center points with iterated Radon points" (PDF), International Journal of Computational Geometry & Applications, 6 (3): 357–377, doi:10.1142/S021819599600023X, MR 1409651.
  • Edelsbrunner, Herbert (1987), Algorithms in Combinatorial Geometry, Berlin: Springer-Verlag, ISBN 0-387-13722-X.
  • Jadhav, S.; Mukhopadhyay, A. (1994), "Computing a centerpoint of a finite planar set of points in linear time", Discrete and Computational Geometry, 12 (1): 291–312, doi:10.1007/BF02574382.
  • Har-Peled, S.; Jones, M. (2020-12-31), "Journey to the Center of the Point Set", ACM Transactions on Algorithms, 17 (1): 9:1–9:21, doi:10.1145/3431285, ISSN 1549-6325.

Read other articles:

Etika internasional

Teori hubungan internasional Realisme Realisme neoklasik Neorealisme (realisme struktural) Realisme klasik Realisme ofensif Realisme defensif Realisme liberal (Mazhab Inggris) Keunggulan relatif Keunggulan absolut Realisme strategis Liberalisme Idealisme Teori perdamaian demokratis Liberalisme republik Institusionalisme Neoliberalisme Liberalisme interdependensi Liberalisme sosiologis Liberalisme institusional Konstruktivisme Konstruktivisme modern Konstruktivisme pascamodern Konstruktivisme ...

 

Cavité souterraine

Galerie ancienne dans une mine de fer de Cabrespine, Aude, France. La notion de cavité souterraine recouvre les concepts de cavité naturelle ou artificielle, située dans le sol ou le sous-sol. Selon le contexte social, une cavité souterraine peut être une possibilité patrimoniale (touristique, scientifique, historique, etc.) ou un risque anthropique (effondrement, pollution, perte de valeur…), dans des proportions diverses. Typologie Selon la région, la nature du sol, la forme, l'ori...

 

Kandagawa Jet Girls

Kandagawa Jet GirlsVisual utama神田川JET GIRLS(Kandagawa Jetto Gāruzu)GenreOlahraga Seri animeSutradaraHiraku KanekoProduserSatoshi MotonagaNoritomo IsogaiShigeto TakeyamaShogo KosakaiChiaki TanimotoSkenarioGō ZappaMusikNoisycroakStudioTNKPelisensiSentai FilmworksSaluranasliAT-X, Tokyo MX, MBS, BS11Tayang 8 Oktober 2019 – 7 Januari 2020Episode12 + OVA[1] PermainanPengembangHoney∞Parade GamesPenerbitJP: MarvelousNA: Xseed GamesEU: Marvelous EuropeAU: Marvelous EuropeGenreBalap...

البطولة الوطنية التونسية 1966–67

البطولة الوطنية التونسية 1966–67 تفاصيل الموسم الرابطة التونسية المحترفة الأولى  النسخة 12  البلد تونس  المنظم الجامعة التونسية لكرة القدم  عدد المشاركين 12   الهداف عبد الوهاب الأحمر (14)[1] البطولة الوطنية التونسية 1965–66  البطولة الوطنية التونسية 1967–68  ت...

 

List of acts of the Parliament of the United Kingdom from 1925

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

 

Tomino

Tomino Vue de Tomino dominant le port de Macinaggio. Administration Pays France Collectivité territoriale unique Corse Circonscription départementale Haute-Corse Arrondissement Bastia Intercommunalité Communauté de communes du Cap Corse Maire Mandat François Orlandi 2020-2026 Code postal 20248 Code commune 2B327 Démographie Gentilé Tominais Populationmunicipale 181 hab. (2021 ) Densité 31 hab./km2 Géographie Coordonnées 42° 56′ 48″ nord, 9° 26′...

EvCard

EvCard电动汽车租赁Company typePrivateIndustryCar rentalFounded2015 (2015)HeadquartersChinaServicesCarsharing EvCard (Chinese: 电动汽车租赁) is a Chinese carsharing company launched in Shanghai by SAIC Group in 2015.[citation needed] Overview EvCard is China's first electric vehicle rental service. As of July 2017, it had around 6,000 cars and 3,000 stations in Shanghai. EvCard also operates in 31 other Chinese cities with 5,200 branches and nearly 30,000 parking l...

 

29th Infantry Division "Piemonte"

29th Infantry Division Piemonte29th Infantry Division Piemonte insigniaActive1939–1943Country Kingdom of ItalyBranch Royal Italian ArmyTypeInfantrySizeDivisionEngagementsWorld War IICommandersNotablecommandersArmellini Chiappi (1939-1940)Rodolfo Torresan (1943)InsigniaIdentificationsymbol Piemonte Division gorget patchesMilitary unit The 29th Infantry Division Piemonte (Italian: 29ª Divisione di fanteria Piemonte) was an infantry division of the Royal Italian Army during Worl...

 

Katedral Luni

Katedral LuniKatedral Santa Mariabahasa Italia: Cattedrale di Santa MariaKatedral LuniLokasiLuniNegaraItaliaDenominasiGereja Katolik RomaArsitekturStatusKatedralStatus fungsionalHancurAdministrasiKeuskupanKeuskupan La Spezia-Sarzana-Brugnato Katedral Luni, sebelumnya Pieve Santa Maria, adalah sebuah reruntuhan gereja katedral Katolik yang terletak di Luni, di Liguria, Italia, dekat pelabuhan. Menurut penemuan arkeologi, gereja ini dibangun oleh Romawi pada akhir abad ke-4 dan awal abad ke...

Oscar Wilde

Oscar WildeOscar WildeLahirOscar Fingal O'Flahertie Wills Wilde(1854-10-16)16 Oktober 1854Dublin, IrlandiaMeninggal30 November 1900(1900-11-30) (umur 46)Paris, PrancisPekerjaanPenulis, Penyair, DramawanBahasaInggris, PrancisKebangsaanIrlandiaAlmamaterKuliah Trinity, Dublin; Kuliah Magdalen, OxfordPeriodeEra VictoriaGenredrama, cerpen, dialog, jurnalismeAliran sastraestetikaKarya terkenalThe Importance of Being Earnest, The Picture of Dorian GrayPasanganConstance Lloyd (1884–1...

 

National Audit Office (United Kingdom)

UK Parliamentary auditing body This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: National Audit Office United Kingdom – news · newspapers · books · scholar · JSTOR (December 2020) (Learn how and when to remove this template message) National Audit OfficeThe National Audit Office's Head Office in Buckingha...

 

Governatorato della Siberia

Governatorato della SiberiaСибирская губерния Suddivisione del Governatorato dell'Impero Russo nel 1682-1762. Il Governatorato della Siberia è indicato con il numero 8. Informazioni generaliCapoluogoTobol'sk Dipendente da Russia AmministrazioneForma amministrativaGovernatorato Evoluzione storicaInizio29 dicembre 1708 CausaIstituzione Fine30 gennaio 1782 CausaDissoluzione Stemma dello Zarato della Siberia (parte dello stemma imperiale russo) Il Governatorato della Siberi...

2012 Samsung Mobile 500

2012 Samsung Mobile 500 Race details[1][2][3] Race 7 of 36 in the 2012 NASCAR Sprint Cup Series Date April 14, 2012 (2012-04-14)Location Texas Motor Speedway in Fort Worth, TexasCourse Permanent racing facility1.5 mi (2.4 km)Distance 334 laps, 501 mi (806.3 km)Weather Scattered thunderstorms; wind out of the south at 21 miles per hour (34 km/h).Average speed 160.577 miles per hour (258.424 km/h)Pole positionDriver Martin Truex Jr. Michael Waltr...

 

Elena Cuza

Princess of the United Principalities Elena CuzaPrincess of the United PrincipalitiesTenure24 January 1859 – 11 February 1866Born(1825-06-17)17 June 1825Iaşi, MoldaviaDied2 April 1909(1909-04-02) (aged 83)Piatra Neamț, RomaniaBurialSolești, RomaniaSpousePrince Alexandru Ioan CuzaHouseCuza (by marriage)FatherIordache RosettiMotherEcaterina SturdzaReligionEastern OrthodoxySignature Elena Cuza (17 June 1825 – 2 April 1909), also known under her semi-official title Elena Doamna, was a...

 

2016年夏季奧林匹克運動會美屬薩摩亞代表團

2016年夏季奥林匹克运动会美属萨摩亚代表團美属萨摩亚旗帜IOC編碼ASANOC美屬薩摩亞國家奧林匹克委員會網站oceaniasport.com/index_id_175.html（英文）2016年夏季奥林匹克运动会（里約熱內盧）2016年8月5日至8月21日運動員4參賽項目3个大项旗手开幕式：塔努馬福利·馬列托亞·江布魯特（举重）[1]闭幕式：Benjamin Waterhouse（柔道）[2]历届奥林匹克运动会参赛记录（总结）夏�...

Suzuki DR-Z400

Type of motorcycle Suzuki DR-Z400ManufacturerSuzukiPredecessorDR350ClassDual-sportEngine398 cc (24.3 cu in) 4-stroke singleBore / stroke90.0 mm × 62.6 mm (3.54 in × 2.46 in)Compression ratio11.3:1Top speed94 mph (151 km/h)[1]Power31.8 hp (23.7 kW)[1] @ 8,400 rpmTorque17.9 lb⋅ft (24.3 N⋅m)[1] @ 5,800 rpmTransmission5-speed manual, constant-mesh, chain-drive[1]Frame typeDia...

 

Lloyd Arabella

Motor vehicle Lloyd Arabella (1959-1961)Borgward Arabella (1961-1963)Lloyd Arabella saloonOverviewManufacturerCarl F. W. Borgward GmbHProduction1959-196147,042 madeBody and chassisBody style2-door saloon 2-door Sport coupé (Frua)LayoutFF layoutPowertrainEngine897 cc Boxer 4-cylinderTransmission4-speed manual Saxomat semi-automatic optionalDimensionsWheelbase2,200 mm (87 in)Length3,800 mm (150 in)Width1,510 mm (59 in)Height1,395 mm (54.9 in)Cu...

 

York Racecourse

Racecourse in North Yorkshire, England York RacecourseA view of the Ebor stand at York RacecourseLocationYork, North YorkshireOwned byYork Racecourse Knavesmire LLPScreened onRacing TVCourse typeFlatNotable racesDante Stakes, Ebor Handicap, International Stakes, Nunthorpe StakesOfficial website York Racecourse is a horse racing venue in York, North Yorkshire, England. It is the third biggest racecourse in Britain in terms of total prize money offered, and second behind Ascot in prize money of...

Gábor Kis

Hungarian water polo player The native form of this personal name is Kis Gábor. This article uses Western name order when mentioning individuals. Gábor KisPersonal informationBorn (1982-09-27) 27 September 1982 (age 41)Budapest, Hungary[1]Nickname KicsiNationality HungarianHeight 1.94 m (6 ft 4+1⁄2 in)Position Centre forwardHandedness RightClub informationCurrent team Invictus (tech. director)Youth career1990–1996 Bp. Spartacus1996– BVSCSenior clubs...

 

Saipem

Saipem S.p.A.JenisSocietà per AzioniKode emitenBIT: SPMKomponen FTSE MIBIndustriJasa ladang minyakDidirikan1957PendiriEnrico MatteiKantorpusatSan Donato Milanese, ItaliaTokohkunciStefano Cao (CEO)Marco Mangiagalli (Chairman)JasaRekayasa dan konstruksi untuk proyek lepas pantai dan darat; operasi rig pengeboran, kapal pengebor, dan FPSOPendapatan €8,526 milyar (2018)[1]Laba operasi €37 juta (2018)[1]Laba bersih €-497 juta (2018)[1]Total aset �...