Vi presenterar ett antal nya resultat på ett av de mest studerade ämnena inom beräkningsgeometri, ortogonal räckviddssökning. Alla våra resultat finns i standardordet RAM-modell: 1. Vi presenterar två datastrukturer för 2D ortogonal räckvidd tomhet. Den första uppnår O(n lg lg n) mellanslag och O(lg lg n) frågetid, förutsatt att n givna punkter är i rank mellanslag. Detta förbättrar de tidigare resultaten från Alstrup, Brodal och Rauhe (FOCS'00), med O(n lg ε n) utrymme och O(lg lg n) frågetid, eller med O (n lg lg n) utrymme och O(lg 2 lg n) frågetid. Vår andra datastruktur använder O(n) utrymme och svarar på frågor i O(lg ε n) tid. Den bästa tidigare O(n)-rymd datastrukturen, på grund av Nekrich (WADS'07), besvarar frågor i O(lg n/ lg lg n) tid. 2. Utgångspunkten är följande: Vi ger en datastruktur för 3D ortogonal intervall rapportering med O(n lg 1+ε n) utrymme och O(lg lg n + k) frågetid för punkter i rank utrymme, för alla konstant ε > 0. Detta förbättrar tidigare resultat av Afshani (ESA'08), Karpinski och Nekrich (COCOON'09) och Chan (SODA'11), med O(n lg 3 n) utrymme och O(lg lg n + k) frågetid, eller med O(n lg 1+ε n) utrymme och O(lg 2 lg n + k) frågetid. Följaktligen får vi förbättrade övre gränser för ortogonal rapportering i alla konstanta dimensioner över 3. Vårt tillvägagångssätt leder också till en ny datastruktur för 2-d ortogonal räckvidd minimala frågor med O(n lg ε n) utrymme och O(lg lg n) frågetid för poäng i rank utrymme. 3. Vad är det som händer? Vi ger en randomiserad algoritm för 4 d offline-dominans rapportering / tomhet med körtid * O (n lg n) plus utdatastorlek. Detta löser två öppna problem (båda dök upp i Preparata och Shamos "seminal bok): a. med tanke på en uppsättning n axeljusterade rektanglar i planet, kan vi rapportera alla k kabinett par (dvs par (r 1, r2) där rektangel r 1 helt omsluter rektangel r2) i O (n lg n + k) förväntad tid; b. med tanke på en uppsättning n punkter i 4 d, kan vi hitta alla maximala punkter (punkter som inte domineras av några andra punkter) i O (n lg n) förväntad tid. Den senaste tidigare utvecklingen på a rapporterades i SoCG'95 av Gupta, Janardan, Smid och Dasgupta, vars huvudsakliga resultat var en O([n lg n + k] lg lg n) algoritm. Det bästa tidigare resultatet på (b) var en O (n lg n lg lg n) algoritm på grund av Gabow, Bentley, och Tarjan-från STOC'84! Som en följd av detta får vi också den aktuella rekordtiden som är knuten till maxima-problemet i alla konstanta dimensioner över 4. Ortogonal sökning, geometriska datastrukturer, dominans, maxima, ord RAM 38] för bara en bråkdel av den stora mängden publikationer på ortogonal sökning. De senaste tidningarna [2, 3] har gjort framsteg när det gäller pekmaskinens modell och I/O-modellen. I denna uppsats studerar vi ortogonal sökning i standardordet RAM-modell, vilket är utan tvekan den mest naturliga och realistiska modellen för beräkning att beakta i det interna minnet. Vi får de bästa RAM övre gränser kända hittills för ett antal problem, inklusive: 2-d ortogonal räckvidd tomhet, 3-d ortogonal räckvidd rapportering, och offline 4-d dominans intervall rapportering.
I synnerhet kan skylinet beräknas i O(n log d−3 n) förväntad tid REF på RAM.
Orthogonal range searching on the RAM, revisited
{'venue': "SoCG '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}