Motiverade av önskan att klara av dataimprecision [31], studerar vi metoder för att dra nytta av preliminär information om punktuppsättningar för att påskynda beräkningen av vissa strukturer i samband med dem. I synnerhet studerar vi följande problem: med tanke på en uppsättning L av n linjer i planet, vi vill förbehandla L så att senare, när vi får en uppsättning P av n punkter, som var och en ligger på en distinkt linje av L, kan vi konstruera konvex skrov P effektivt. Vi visar att i kvadratisk tid och rum är det möjligt att konstruera en datastruktur på L som gör det möjligt för oss att beräkna konvexa skrov av någon sådan punkt som P i O(nα(n) log * n) förväntad tid. Om vi vidare utgår från att punkterna är "omedvetna" med avseende på datastrukturen, förbättras körtiden till O(nα(n)). Samma resultat gäller när L är en uppsättning linjesegment (i allmänhet). Vi presenterar flera förlängningar, inklusive en avvägning mellan utrymme och frågetid och en utgångskänslig algoritm. Vi studerar också det "dubbla problemet" där vi visar hur vi effektivt beräknar (≤ k)-nivån av n-linjer i planet, som var och en är incident till en distinkt punkt (ges i förväg). Vi kompletterar våra resultat med en lägre gräns (n log n) under den algebraiska beräkning trädmodellen för flera relaterade problem, inklusive sortering av en uppsättning punkter (enligt t.ex. deras x-ordning), som var och en ligger på en given linje känd i förväg. Därför är konvexa skrov problem under vår inställning lättare än sortering, i motsats till "standard" konvexa skrov och sorteringsproblem, där de två problemen kräver  till (n log n) steg i värsta fall (enligt algebraiska beräkning trädmodellen).
Detta resultat utvidgades senare till 8 godtyckliga osammanhängande regioner i planet av van REF visar hur man prebehandlar 13 en uppsättning linjer i planet så att konvexa skrov av en uppsättning punkter med en 14 punkt på varje linje kan beräknas snabbare än n log n tid.
Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing
{'venue': 'Computational Geometry: Theory and Applications (CGTA), 46(4), 2013, pp. 417-434', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}