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.
Slutligen, Vi noterar att en datastruktur för intervall föregångare frågor omedelbart innebär en för den klassiska och mycket studerade 2D ortogonal intervall rapportering problem från beräkning geometri REF,
Orthogonal range searching on the RAM, revisited
{'venue': "SoCG '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}