On the minimum total length of interval systems expressing all intervals, and range-restricted queries
SCIE
SCOPUS
- Title
- On the minimum total length of interval systems expressing all intervals, and range-restricted queries
- Authors
- Ahn, HK; Brass, P; Na, HS; Shin, CS
- Date Issued
- 2009-04
- Publisher
- ELSEVIER SCIENCE BV
- Abstract
- In this paper, we study the classical one-dimensional range-searching problem, i.e., expressing any interval {i, .... j} subset of {1, ..., n} as a disjoint union of at most k intervals in a system of intervals, though with a different lens: we are interested in the minimum total length of the intervals in such a system (and not their number, as is the concern traditionally). We show that the minimum total length of a system of intervals in {1, ..., n} that allows to express any interval as a disjoint union of at most k intervals of the system is Theta(n(1+2/k)) for any fixed k. We also prove that the minimum number of intervals k = k(n, c), for which there exists a system of intervals of total length cn with that property, satisfies k(n, c) = Theta(n(1/c)) for any integer c >= 1. We also discuss the situation when k = Theta(log n). (c) 2008 Elsevier B.V. All rights reserved.
- Keywords
- Interval system; Query; Minimum total length; LOWER BOUNDS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29121
- DOI
- 10.1016/j.comgeo.2008.03.004
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 42, no. 3, page. 207 - 213, 2009-04
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.