Generalized static orthogonal range searching in less space

Christian Worm  Mortensen

Generalized static orthogonal range searching in less space

Christian Worm Mortensen

Research output: Book / Anthology / Report › Report › Research

Abstract

We reduce the space usage on two problems related to generalized orthogonal range searching by almost a logarithmic factor. Our main result is that the generalized static orthogonal segment intersection reporting problem for n segment on an n times n grid can be solved in time O(log 2 log n + k) for queries using space O(n log log n). Here k is the number of reported segments.

Original language	English

Place of Publication	Copenhagen
Publisher	IT-Universitetet i København
Edition	TR-2003-33
Number of pages	11
ISBN (Electronic)	87-7949-046-8
Publication status	Published - Sept 2003
Externally published	Yes

Series	IT University Technical Report Series
Number	TR-2003-33
ISSN	1600-6100

Access to Document

ITU-TR-2003-33 pdfFinal published version, 170 KB

Cite this

@book{68ff98aaa5dc4ab2a0d8d8367f780149,

title = "Generalized static orthogonal range searching in less space",

abstract = "We reduce the space usage on two problems related to generalized orthogonal range searching by almost a logarithmic factor. Our main result is that the generalized static orthogonal segment intersection reporting problem for n segment on an n times n grid can be solved in time O(log 2 log n + k) for queries using space O(n log log n). Here k is the number of reported segments.",

author = "Mortensen, {Christian Worm}",

year = "2003",

month = sep,

language = "English",

series = "IT University Technical Report Series",

number = "TR-2003-33",

publisher = "IT-Universitetet i K{\o}benhavn",

address = "Denmark",

edition = "TR-2003-33",

}

TY - RPRT

T1 - Generalized static orthogonal range searching in less space

AU - Mortensen, Christian Worm

PY - 2003/9

Y1 - 2003/9

N2 - We reduce the space usage on two problems related to generalized orthogonal range searching by almost a logarithmic factor. Our main result is that the generalized static orthogonal segment intersection reporting problem for n segment on an n times n grid can be solved in time O(log 2 log n + k) for queries using space O(n log log n). Here k is the number of reported segments.

AB - We reduce the space usage on two problems related to generalized orthogonal range searching by almost a logarithmic factor. Our main result is that the generalized static orthogonal segment intersection reporting problem for n segment on an n times n grid can be solved in time O(log 2 log n + k) for queries using space O(n log log n). Here k is the number of reported segments.

M3 - Report

T3 - IT University Technical Report Series

BT - Generalized static orthogonal range searching in less space

PB - IT-Universitetet i København

CY - Copenhagen

ER -

Generalized static orthogonal range searching in less space

Abstract

Access to Document

Fingerprint

Cite this