Konvexa lager

De konvexa lagren i en punktuppsättning och deras skärning med ett halvplan

I beräkningsgeometri är de konvexa lagren av en uppsättning punkter i det euklidiska planet en sekvens av kapslade konvexa polygoner med punkterna som sina hörn. Den yttersta är spetsarnas konvexa skrov och resten är formade på samma sätt rekursivt . Det innersta lagret kan vara degenererat, endast bestående av en eller två punkter. Problemet med att konstruera konvexa lager har också kallats för lökskalning eller löknedbrytning .

$) {\displaystyle O(n\log n)}$ skrov, är det möjligt att dela upp vilken uppsättning av ${\displaystyle n} som helst$ i dess konvexa skikt i tiden .

En tidig tillämpning av de konvexa lagren var i robust statistik , som ett sätt att identifiera extremvärden och mäta den centrala tendensen hos en uppsättning provpunkter. I detta sammanhang kallas antalet konvexa lager som omger en given punkt dess konvexa skrovskalningsdjup , och själva de konvexa lagren är djupkonturerna för denna uppfattning om datadjup.

Konvexa lager kan användas som en del av en effektiv intervallrapporteringsdatastruktur för att lista alla punkter i ett frågehalvplan . Punkterna i halvplanet från varje efterföljande lager kan hittas genom en binär sökning för att hitta den mest extrema punkten i halvplanets riktning, och sedan söka sekventiellt därifrån. Fractional cascading kan användas för att påskynda binära sökningar, vilket ger total frågetid $O(\log n+k)$ för att hitta $k$ punkter ur en uppsättning av $n$ .

Punkterna i ett $n\times n$ rutnät har $\Theta (n^{4/3})$ konvexa lager, liksom samma antal likformigt slumpmässiga lager punkter inom någon konvex form.