Centerpoint (geometri)

I statistik och beräkningsgeometri är begreppet mittpunkt en generalisering av medianen till data i högre dimensionell euklidisk rymd . Givet en uppsättning punkter i d -dimensionell rymd, är en mittpunkt av mängden en punkt så att varje hyperplan som går genom den punkten delar uppsättningen av punkter i två ungefär lika stora delmängder: den mindre delen bör ha minst en 1/( d + 1) bråkdel av punkterna. Liksom medianen behöver inte en mittpunkt vara en av datapunkterna. Varje icke-tom uppsättning punkter (utan dubbletter) har minst en mittpunkt.

Relaterade begrepp

Närliggande begrepp är Tukey-djupet för en punkt (minsta antalet provpunkter på ena sidan av ett hyperplan genom punkten) och en Tukey-median för en punktuppsättning (en punkt som maximerar Tukey-djupet). En mittpunkt är en djuppunkt åtminstone n /( d + 1), och en Tukey-median måste vara en mittpunkt, men inte varje mittpunkt är en Tukey-median. Båda termerna är uppkallade efter John Tukey .

För en annan generalisering av medianen till högre dimensioner, se geometrisk median .

Existens

Ett enkelt bevis på förekomsten av en mittpunkt kan erhållas med hjälp av Hellys sats . Anta att det finns n punkter, och betrakta familjen av slutna halvrum som innehåller mer än dn /( d + 1) av punkterna. Färre än n /( d + 1) punkter är exkluderade från någon av dessa halvrum, så skärningspunkten för en delmängd av d + 1 av dessa halvrum måste vara tom. Av Hellys teorem följer att skärningspunkten mellan alla dessa halvrum också måste vara tom. Varje punkt i denna skärningspunkt är nödvändigtvis en mittpunkt.

Algoritmer

För punkter i det euklidiska planet kan en mittpunkt konstrueras i linjär tid . I vilken dimension d som helst kan en Tukey median (och därför också en mittpunkt) konstrueras i tiden O( n ^{d − 1} + n log n ).

En randomiserad algoritm som upprepade gånger ersätter uppsättningar av d + 2 punkter med deras radonpunkt kan användas för att beräkna en approximation till en mittpunkt för vilken punktuppsättning som helst, i den meningen att dess Tukey-djup är linjärt i urvalsuppsättningens storlek, i en mängd av tid som är polynom i både antalet punkter och dimensionen.

Källor

• Chan, Timothy M. (2004), "En optimal randomiserad algoritm för maximalt Tukey-djup", Proc. 15:e ACM–SIAM Symp. om diskreta algoritmer (SODA 2004) , s. 430–436 .
•   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, 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 .