Abstract
The complexity of two related geometrical (indeed, combinatorial) problems is considered, measured by the number of queries needed to determine the solution. It is proved that one cannot check in a linear in N number of queries whether N intervals cover a whole interval, or whether for N pairs of intervals on two lines there is a pair of points intersecting each of these pairs of intervals ("piercing all pairs of intervals"). The proofs are related to examples which show that there is no "Helly property" here - the whole set of N may cover the whole interval (resp. may have no pair of points piercing all pairs of intervals) while any proper subset does not. Also, for the piercing problem we outline an algorithm, taking O(N log N) steps, to check whether there is a pair of points piercing all pairs of intervals and if there is, to find it.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.