Vi studerar datageometriska problem på osäkra punkter. En osäker punkt är en punkt som inte har en fast plats, utan snarare beskrivs med en sannolikhetsfördelning. När dessa sannolikhetsfördelningar är begränsade till ett begränsat antal platser kallas punkterna obeslutsamma punkter. I synnerhet fokuserar vi på problem med geometriska former och på att bygga kompakta distributioner för att beskriva hur lösningarna på dessa problem varierar med hänsyn till osäkerheten i punkterna. Våra huvudsakliga resultat är: (1) en enkel och effektiv randomiserad approximationsalgoritm för att beräkna fördelningen av statistik på osäkra datamängder; (2) en polynomisk, deterministisk och exakt algoritm för att beräkna fördelningen av svar för alla LP-typ problem på en obeslutsam punktuppsättning; och (3) utvecklingen av form sannolikhet (SIP) funktioner som fångar den omgivande fördelningen av former passar osäkra eller obeslutsamma punktuppsättningar och är tillåtna för de två algoritmiska konstruktioner.
I denna mer allmänna modell och andra, Jorgensen m.fl. REF undersökte approximationer av fördelningsfunktionerna hos lösningarna på problem med geometrisk formsättning och beskrev variationen av lösningarna på dessa problem med avseende på osäkerheten i punkterna.
Geometric Computations on Indecisive and Uncertain Points
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}