Convex Hull and Variants: Output sensitivity
Jérémy Barbay 8 Abr 201008/04/10 a las 14:13 hrs.2010-04-08 14:13:08
**** Convex Hull and Variants: Output sensitivity
<2010-04-08 Thu 14:30-16:00>
1) What we saw
- adaptive analysis
- papers to read
- tarea: order adaptive convex hull and max vector?
2) Planar Convex Hull: the odyssey
1. Gift Wrapping $O(nh)\subsetO(n^2)$
- (choose tangent of minimal angle)
2. Graham's scan $O(\mbox{sorting}(n)+n) \subset O(n\lg n)$
3. Kirkpatrick and Seidel $O(n\lg h) \subset O(n\lg n)$
4. Vertical Partitioning $O(n H_v) \subset O(n\lg h)$
5. Instance Optimality $O(n H) \subset O(nH_v)$
- $\Theta(nH)$ for restricted class of algorithms
3) Extensions and Open Pbs
1. Summary
2. Extensions
- Sorting, max vector (...)
- 3D Convex Hull, Reporting/Counting Pbs in 2D
3. Open Pbs:
- more general class of algorithms
- Input Order adaptivity + Instance Optimality?
***** References:
@article{optimalOutputSensitiveConvexHullAlgorithmsInTwoAndThreeDimensions,
author = "Timothy Chan",
title = "Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions",
journal = "GEOMETRY: Discrete \& Computational Geometry",
volume = 16,
year = 1996,
url = "citeseer.ist.psu.edu/ ... e/chan96optimal.html"
}
@article{ chan01dynamic,
author = "Timothy M. Chan",
title = "Dynamic planar convex hull operations in near-logarithmic amortized time",
journal = "Journal of the ACM",
volume = "48",
number = "1",
pages = "1--12",
year = "2001",
url = "citeseer.ist.psu.edu/ ... e/chan00dynamic.html"
}
@InProceedings{instanceOptimalGeometricAlgorithmsFOCS,
author = {Peyman Afshani and Jeremy Barbay and Timothy Chan},
title = {Instance-optimal geometric algorithms},
booktitle = {Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS)},
year = 2009,
note = {2009-FOCS-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan.pdf},
annote = {Preliminary version on www.cs.uwaterloo.ca/~tmchan/abc_4_09.ps},
abstract = {We prove the existence of an algorithm A for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A' in a certain class C, the maximum running time of A on input s_1,...,s_n is at most a constant factor times the maximum running time of A' on s_1,...,s_n, where the maximum is taken over all permutations s_1,...,s_n of S. In fact, we can establish a stronger property: for every S and A', the maximum running time of A is at most a constant factor times the average running time of A' over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order.
The class C under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap (1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm.
To demonstrate the potential of the concept, we further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, finding bichromatic L_\infty-close pairs in 2-d, off-line orthogonal range searching in 2-d, off-line dominance reporting in 2-d and 3-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d.
}
}
<2010-04-08 Thu 14:30-16:00>
1) What we saw
- adaptive analysis
- papers to read
- tarea: order adaptive convex hull and max vector?
2) Planar Convex Hull: the odyssey
1. Gift Wrapping $O(nh)\subsetO(n^2)$
- (choose tangent of minimal angle)
2. Graham's scan $O(\mbox{sorting}(n)+n) \subset O(n\lg n)$
3. Kirkpatrick and Seidel $O(n\lg h) \subset O(n\lg n)$
4. Vertical Partitioning $O(n H_v) \subset O(n\lg h)$
5. Instance Optimality $O(n H) \subset O(nH_v)$
- $\Theta(nH)$ for restricted class of algorithms
3) Extensions and Open Pbs
1. Summary
2. Extensions
- Sorting, max vector (...)
- 3D Convex Hull, Reporting/Counting Pbs in 2D
3. Open Pbs:
- more general class of algorithms
- Input Order adaptivity + Instance Optimality?
***** References:
@article{optimalOutputSensitiveConvexHullAlgorithmsInTwoAndThreeDimensions,
author = "Timothy Chan",
title = "Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions",
journal = "GEOMETRY: Discrete \& Computational Geometry",
volume = 16,
year = 1996,
url = "citeseer.ist.psu.edu/ ... e/chan96optimal.html"
}
@article{ chan01dynamic,
author = "Timothy M. Chan",
title = "Dynamic planar convex hull operations in near-logarithmic amortized time",
journal = "Journal of the ACM",
volume = "48",
number = "1",
pages = "1--12",
year = "2001",
url = "citeseer.ist.psu.edu/ ... e/chan00dynamic.html"
}
@InProceedings{instanceOptimalGeometricAlgorithmsFOCS,
author = {Peyman Afshani and Jeremy Barbay and Timothy Chan},
title = {Instance-optimal geometric algorithms},
booktitle = {Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS)},
year = 2009,
note = {2009-FOCS-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan.pdf},
annote = {Preliminary version on www.cs.uwaterloo.ca/~tmchan/abc_4_09.ps},
abstract = {We prove the existence of an algorithm A for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A' in a certain class C, the maximum running time of A on input s_1,...,s_n is at most a constant factor times the maximum running time of A' on s_1,...,s_n, where the maximum is taken over all permutations s_1,...,s_n of S. In fact, we can establish a stronger property: for every S and A', the maximum running time of A is at most a constant factor times the average running time of A' over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order.
The class C under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap (1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm.
To demonstrate the potential of the concept, we further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, finding bichromatic L_\infty-close pairs in 2-d, off-line orthogonal range searching in 2-d, off-line dominance reporting in 2-d and 3-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d.
}
}
| Última Modificación | 8 Abr 201008/04/10 a las 14:13 hrs.2010-04-08 14:13:08 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
