S vara en uppsättning n punkter i Euclidean planet. De konvexa skikten av S är konvexa polygoner som erhålls genom iterering enligt följande förfarande: beräkna konvexa skrov av S och ta bort dess hörn från S. Denna process att skala en planar punktuppsättning är central i studien av robusta estimatorer i statistik. Den ger också värdefull information om morfologin på en uppsättning webbplatser och har visat sig vara en effektiv förutsättning för problem med räckviddssökning. En optimal algoritm beskrivs för att beräkna konvexa lager av S. Algoritmen körs i O( n log n) tid och kräver O(n) utrymme. Även adresserat är problemet med att bestämma djupet av en frågepunkt inom konvexa lager av S, dvs antalet lager som omger frågepunkten. Detta är i grund och botten ett problem med lokaliseringen av plana punkter, för vilka man därför känner till optimala lösningar. Att dra nytta av strukturella egenskaper hos problemet, men en mycket enklare optimal lösning härleds.
En optimal algoritm för att hitta alla konvexa lager med runtime O (n log n) presenteras i REF.
On the convex layers of a planar set
{'venue': 'IEEE Transactions on Information Theory', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}