Interval stabbing problems in small integer ranges

Publikationstyp
Conference Paper
Date Issued
2009
Sprache
English
Author(s)
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7651
First published in
Lecture notes in computer science  
Number in series
5878 LNCS
Start Page
163
End Page
172
Citation
International Symposium on Algorithms and Computation (ISAAC 2009)
Publisher DOI
10.1007/978-3-642-10631-6_18
Scopus ID
2-s2.0-75649147043
Publisher
Springer
Given a set I of n intervals, a stabbing query consists of a point q and asks for all intervals in I that contain q. The Interval Stabbing Problem is to find a data structure that can handle stabbing queries efficiently. We propose a new, simple and optimal approach for different kinds of interval stabbing problems in a static setting where the query points and interval ends are in 1,⋯,O(n).
Subjects
Discrete
Interval intersection
Interval stabbing
Point enclosure
Static
DDC Class
004: Informatik