Mathematics – Combinatorics
Scientific paper
2011-09-13
Mathematics
Combinatorics
8 pages, 2 figures
Scientific paper
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.
Katchalski Meir
Levy Eliahu
No associations
LandOfFree
No O(N) queries for checking if N intervals cover everything or for piercing N pairs of intervals. An O(N log N)-steps algorithm for piercing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with No O(N) queries for checking if N intervals cover everything or for piercing N pairs of intervals. An O(N log N)-steps algorithm for piercing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and No O(N) queries for checking if N intervals cover everything or for piercing N pairs of intervals. An O(N log N)-steps algorithm for piercing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-333659