CPS 234: Summary of Lectures
Pankaj K. Agarwal
RAM model of
computation, its advantages and
disadvantages [PS85, Chapter 1,];
pointer-machine model [Tar83];
semigroup model [Fre81], power of subtraction,
partial-sum query.
Yao [Yao82] has shown that a partial-sum query under the
semigroup model can be answered in
time;
a matching lower
bound is proved by Chazelle and Rosenberg
[CR89].
Algebraic decision tree
model [PS85, Chapter 2,]; Ben Or's
theorem [PS85, Chapter 2,],
[SY82].
Ben Or's theorem is extended to integer
inputs is given in [Yao91];
generalization and stronger bounds on decision
tree models are given in [BLY93, Yao94, BO94].
References
- BLY93
-
Anders Björner, László Lovász, and Andrew Chi-Chih Yao.
Linear decision trees: Volume estimates and topological bounds.
In Proc. 24th Annu. ACM Sympos. Theory Comput., pages 170-177,
1993.
- BO94
-
Michael Ben-Or.
Algebraic computation trees in characteristi p>0.
In Proc. 35th Annual Symposium on Foundations of Computer
Science, pages 534-539, 1994.
- CR89
-
B. Chazelle and B. Rosenberg.
Computing partial sums in multidimensional arrays.
In Proc. 5th Annu. ACM Sympos. Comput. Geom., pages 131-139,
1989.
- Fre81
-
M. L. Fredman.
A lower bound on the complexity of orthogonal range queries.
J. ACM, 28:696-705, 1981.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
- SY82
-
J. M. Steele and A. C. Yao.
Lower bounds for algebraic decision trees.
J. Algorithms, 3:1-8, 1982.
- Tar83
-
R. E. Tarjan.
Data Structures and Network Algorithms, volume 44 of
CBMS-NSF Regional Conference Series in Applied Mathematics.
Society for Industrial Applied Mathematics, 1983.
- Yao82
-
A. C. Yao.
Space-time trade-off for answering range queries.
In Proc. 14th Annu. ACM Sympos. Theory Comput., pages 128-136,
1982.
- Yao91
-
A. C. Yao.
Lower bounds for algebraic computation trees with integer inputs.
SIAM J. Comput., 20:655-668, 1991.
- Yao94
-
Andrew Chi-Chih Yao.
Decision tree complexity and betti numbers.
In Proc. 25th Annu. ACM Sympos. Theory Comput., 1994.
Segment trees
[PS85, Section 1.2.3,],
interval trees [PS85, Section-8.2,], priority search trees
[McC85, IKO88];
interval queries, ground rectangle queries;
Intersection
reporting, naive algorithm, line sweep
[BO79, Bro81];
intersection counting.
The best known algorithm for segment-intersection counting
runs in time roughly
[GOS88, Aga90, Cha93].
Developing a faster algorithm, proving a nontrivial lower
bound, is a challenging open problem.
References
- Aga90
-
Pankaj K. Agarwal.
Partitioning arrangements of lines: II. Applications.
Discrete Comput. Geom., 5:533-573, 1990.
- BO79
-
J. L. Bentley and T. A. Ottmann.
Algorithms for reporting and counting geometric intersections.
IEEE Trans. Comput., C-28:643-647, 1979.
- Bro81
-
K. Q. Brown.
Comments on ``Algorithms for reporting and counting geometric
intersections''.
IEEE Trans. Comput., C-30:147-148, 1981.
- Cha93
-
B. Chazelle.
Cutting hyperplanes for divide-and-conquer.
Discrete Comput. Geom., 9(2):145-158, 1993.
- GOS88
-
L. Guibas, M. Overmars, and M. Sharir.
Intersecting line segments, ray shooting, and other applications of
geometric partitioning techniques.
In Proc. 1st Scand. Workshop Algorithm Theory, volume 318 of
Lecture Notes in Computer Science, pages 64-73. Springer-Verlag, 1988.
- IKO88
-
C. Icking, R. Klein, and T. Ottmann.
Priority search trees in secondary memory.
In Proc. Internat. Workshop Graph-Theoret. Concepts Comput. Sci.
(WG '87), volume 314 of Lecture Notes in Computer Science, pages
84-93. Springer-Verlag, 1988.
- McC85
-
E. M. McCreight.
Priority search trees.
SIAM J. Comput., 14:257-276, 1985.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
Basic
line-sweep algorithm [BO79], modification by Brown
to improve the space complexity [Bro81].
A better bound on the size of the priority queue was proved by
Pach and Sharir [PS91]. Randomized optimal
algorithms for segment intersection reporting are given in
[CS89, Mul90, Mul91], and deterministic
optimal algorithms are proposed in
[CE92, Bal95].
Definition, Graham scan algorithm, Jarvis march, quick hull,
computing tangents and point location, on-line algorithm.
All this material can be found in Chapter 3 of Preparata and
Shamos [PS85]. An optimal
-time algorithm is
due to Chan [Cha95]; see also [KS86]
for an earlier, more complex optimal algorithm.
Convex hull of a simple polygon can be computed in linear time
[GY83].
References
- Bal95
-
Ivan J. Balaban.
An optimal algorithm for finding segment intersections.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 211-219,
1995.
- BO79
-
J. L. Bentley and T. A. Ottmann.
Algorithms for reporting and counting geometric intersections.
IEEE Trans. Comput., C-28:643-647, 1979.
- Bro81
-
K. Q. Brown.
Comments on ``Algorithms for reporting and counting geometric
intersections''.
IEEE Trans. Comput., C-30:147-148, 1981.
- CE92
-
B. Chazelle and H. Edelsbrunner.
An optimal algorithm for intersecting line segments in the plane.
J. ACM, 39:1-54, 1992.
- Cha95
-
Timothy M. Y. Chan.
Output-sensitive results on convex hulls, extreme points, and related
problems.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 10-19,
1995.
- CS89
-
K. L. Clarkson and P. W. Shor.
Applications of random sampling in computational geometry, II.
Discrete Comput. Geom., 4:387-421, 1989.
- GY83
-
R. L. Graham and F. F. Yao.
Finding the convex hull of a simple polygon.
J. Algorithms, 4:324-331, 1983.
- KS86
-
D. G. Kirkpatrick and R. Seidel.
The ultimate planar convex hull algorithm?
SIAM J. Comput., 15:287-299, 1986.
- Mul90
-
K. Mulmuley.
A fast planar partition algorithm, I.
Journal of Symbolic Computation, 10(3/4):253-280, 1990.
- Mul91
-
K. Mulmuley.
A fast planar partition algorithm, II.
J. ACM, 38:74-103, 1991.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
- PS91
-
J. Pach and M. Sharir.
On vertical visibility in arrangements of segments and the queue size
in the Bentley-Ottman line sweeping algorithm.
SIAM J. Comput., 20:460-470, 1991.
Definition, faces, examples of polytopes, moment curve,
upper-bound theorem (complexity of a convex d-polytope), duality.
The book by Ziegler is an excellent treatise on convex polytopes
[Zie94]. See also the books by Edelsbrunner [Ede87].
A simple proof of the upper-bound theorem is given by Seidel
[Sei95].
Incremental algorithm (also known as the beneath-beyond
method) [PS85, Section3.4,], finer analysis of the
incremental algorithm [Sei81], [Ede87, Section8.4,],
divide-and-conquer algorithm [Ede87, Section8.5,].
References
- Ede87
-
H. Edelsbrunner.
Algorithms in Combinatorial Geometry, volume 10 of EATCS
Monographs on Theoretical Computer Science.
Springer-Verlag, Heidelberg, 1987.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
- Sei81
-
R. Seidel.
A convex hull algorithm optimal for point sets in even dimensions.
M.Sc. thesis, Dept. Comput. Sci., Univ. British Columbia,
Vancouver, BC, 1981.
Report 81/14.
- Sei95
-
R. Seidel.
The upper bound theorem for polytopes: an easy proof of its
asymptotic version.
Comput. Geom. Theory Appl., 5:115-116, 1995.
- Zie94
-
G. M. Ziegler.
Lectures on Polytopes, volume 152 of Graduate Texts in
Mathematics.
Springer-Verlag, 1994.
A randomized incremental algorithm for computing the convex hull
of a set of points in d-space with expected running
time
.
The original algorithms is by
Clarkson and Shor [CS89] and Seidel
[Sei91].
The algorithm presented in the class is based on the
exposition in [MR95, Mul94].
These algorithms were derandomized by Chazelle
[Cha93] and subsequently simplified by
Brönnimann et al. [BCM93].
See [AGR94] for a parallel convex hull algorithms
based on Chazelle's algorithm.
References
- AGR94
-
N. M. Amato, M. T. Goodrich, and E. A. Ramos.
Parallel algorithms for higher-dimensional convex hulls.
In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., pages
683-694, 1994.
- BCM93
-
Hervé Brönnimann, Bernard Chazelle, and Jir´i Matousek.
Product range spaces, sensitive sampling, and derandomization.
In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci., pages
400-409, 1993.
- Cha93
-
B. Chazelle.
An optimal convex hull algorithm in any fixed dimension.
Discrete Comput. Geom., 10:377-409, 1993.
- CS89
-
K. L. Clarkson and P. W. Shor.
Applications of random sampling in computational geometry, II.
Discrete Comput. Geom., 4:387-421, 1989.
- MR95
-
R. Motwani and P. Raghavan.
Randomized Algorithms.
Cambridge University Press, New York, NY, 1995.
- Mul94
-
K. Mulmuley.
Computational Geometry: An Introduction Through Randomized
Algorithms.
Prentice Hall, Englewood Cliffs, NJ, 1994.
- Sei91
-
R. Seidel.
Small-dimensional linear programming and convex hulls made easy.
Discrete Comput. Geom., 6:423-434, 1991.
A randomized incremental algorithm, with
expected time, for reporting all
k intersection points in a set of n segments.
Such algorithms are described in
[CS89, Mul90, Mul91, CEG
93].
Deterministic algorithms with the same time are presented in
[CE92, Bal95].
Antipodal pairs, normal diagram, diameter and width in 2D.
Randomized algorithm for computing the diameter of a point set
in 3D [CS89]. Near-linear-time deterministic
algorithms for computing the diameter in 3D are presented in
[CEGS93, MS96, Ram96, AGR94].
References
- AGR94
-
N. M. Amato, M. T. Goodrich, and E. A. Ramos.
Parallel algorithms for higher-dimensional convex hulls.
In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., pages
683-694, 1994.
- Bal95
-
Ivan J. Balaban.
An optimal algorithm for finding segment intersections.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 211-219,
1995.
- CE92
-
B. Chazelle and H. Edelsbrunner.
An optimal algorithm for intersecting line segments in the plane.
J. ACM, 39:1-54, 1992.
- CEG
93 -
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink.
Computing a face in an arrangement of line segments and related
problems.
SIAM J. Comput., 22:1286-1302, 1993.
- CEGS93
-
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir.
Diameter, width, closest line pair and parametric searching.
Discrete Comput. Geom., 10:183-196, 1993.
- CS89
-
K. L. Clarkson and P. W. Shor.
Applications of random sampling in computational geometry, II.
Discrete Comput. Geom., 4:387-421, 1989.
- MS96
-
J. Matousek and O. Schwarzkopf.
A deterministic algorithm for the three-dimensional diameter problem.
Comput. Geom. Theory Appl., 6:253-262, 1996.
- Mul90
-
K. Mulmuley.
A fast planar partition algorithm, I.
Journal of Symbolic Computation, 10(3/4):253-280, 1990.
- Mul91
-
K. Mulmuley.
A fast planar partition algorithm, II.
J. ACM, 38:74-103, 1991.
- Ram96
-
E. Ramos.
Intersection of unit-balls and diameter of a point set in
.
Computat. Geom. Theory Appl., 6:in press, 1996.
Definition, properties of Voronoi diagrams, Delaunay
triangulation, relationship between Voronoi diagrams and
convex hulls, randomized incremental algorithm.
There are a number of survey papers on Voronoi diagrams, see
e.g. [Aur91, For92]. The first
time algorithm was developed by Shamos and Hoey
[SH75]; see also [PS85].
A sweep-line algorithm for
computing the Voronoi diagram of a set of points in the plane
was given by Fortune [For87].
The relationship between Voronoi diagrams and lower envelopes
is described in [ES86, SA95].
See
[Aur91, AS95, BSTY95, CKS
95, CKS
95]
and the references therein for some references on Voronoi
diagrams of point objects.
The randomized incremental algorithm described in the class is
by Guibas et al. [GKS92]. See also
[Che86],
References
- AS95
-
Helmut Alt and Otfried Schwarzkopf.
The Voronoi diagram of curved objects.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 89-97,
1995.
- Aur91
-
F. Aurenhammer.
Voronoi diagrams: A survey of a fundamental geometric data structure.
ACM Comput. Surv., 23:345-405, 1991.
- BSTY95
-
Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec.
Voronoi diagrams in higher dimensions under certain polyhedral
distance functions.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 79-88,
1995.
- Che86
-
L. P. Chew.
Building Voronoi diagrams for convex polygons in linear expected
time.
Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth
College, Hanover, NH, 1986.
- CKS
95 -
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, and Emo Welzl.
Voronoi diagrams of lines in 3-space under polyhedral convex distance
functions.
In Proc. 6th ACM-SIAM Sympos. Discrete Algorithms, pages
197-204, 1995.
- ES86
-
H. Edelsbrunner and R. Seidel.
Voronoi diagrams and arrangements.
Discrete Comput. Geom., 1:25-44, 1986.
- For87
-
S. J. Fortune.
A sweepline algorithm for Voronoi diagrams.
Algorithmica, 2:153-174, 1987.
- For92
-
S. Fortune.
Voronoi diagrams and Delaunay triangulations.
In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean
Geometry, volume 1 of Lecture Notes Series on Computing, pages
193-233. World Scientific, Singapore, 1992.
- GKS92
-
L. J. Guibas, D. E. Knuth, and M. Sharir.
Randomized incremental construction of Delaunay and Voronoi
diagrams.
Algorithmica, 7:381-413, 1992.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
- SA95
-
M. Sharir and P. K. Agarwal.
Davenport-Schinzel Sequences and Their Geometric
Applications.
Cambridge University Press, New York, 1995.
- SH75
-
M. I. Shamos and D. Hoey.
Closest-point problems.
In Proc. 16th Annu. IEEE Sympos. Found. Comput. Sci., pages
151-162, 1975.
Slab method, persistent data structure, amortized complexity.
The material was taken from the paper by Sarnak and Tarjan
[ST86]. The data structure describe here is
partially persistent, in the sense that one is not allowed to
make changes in the earlier versions of the data structure.
See [DSST89] for a fully persistent data structure.
Monotone chain method, improving the space complexity,
improving the query time, fractional cascading.
The material covered here can be found in Chapter 2 of the
textbook. The improvement in the query time was proposed by
Edelsbrunner et al. [EGS86]. The general
fractional cascading was introduced by Chazelle and Guibas
[CG86a, CG86b]. A dynamic version was proposed
by Mehlhorn and Näher [MN90]; see also
[Sen92].
Preparata and Tamassia dynamized the monotone-chain method
[PT90, PT89, TP90]. By adding
persistence to their dyanmic data structures they obtained a
three-dimensional point-location data structure
[PT92].
References
- CG86a
-
B. Chazelle and L. J. Guibas.
Fractional cascading: I. A data structuring technique.
Algorithmica, 1:133-162, 1986.
- CG86b
-
B. Chazelle and L. J. Guibas.
Fractional cascading: II. Applications.
Algorithmica, 1:163-191, 1986.
- DSST89
-
J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan.
Making data structures persistent.
J. Comput. Syst. Sci., 38:86-124, 1989.
- EGS86
-
H. Edelsbrunner, L. J. Guibas, and J. Stolfi.
Optimal point location in a monotone subdivision.
SIAM J. Comput., 15:317-340, 1986.
- MN90
-
K. Mehlhorn and S. Näher.
Dynamic fractional cascading.
Algorithmica, 5:215-241, 1990.
- PT89
-
F. P. Preparata and R. Tamassia.
Fully dynamic point location in a monotone subdivision.
SIAM J. Comput., 18:811-830, 1989.
- PT90
-
F. P. Preparata and R. Tamassia.
Dynamic planar point location with optimal query time.
Theoret. Comput. Sci., 74:95-114, 1990.
- PT92
-
F. P. Preparata and R. Tamassia.
Efficient point location in a convex spatial cell-complex.
SIAM J. Comput., 21:267-280, 1992.
- Sen92
-
S. Sen.
Fractional cascading simplified.
In Proc. 3rd Scand. Workshop Algorithm Theory, volume 621 of
Lecture Notes in Computer Science, pages 212-220. Springer-Verlag,
1992.
- ST86
-
N. Sarnak and R. E. Tarjan.
Planar point location using persistent search trees.
Commun. ACM, 29:669-679, 1986.
- TP90
-
R. Tamassia and F. P. Preparata.
Dynamic maintenance of planar digraphs, with applications.
Algorithmica, 5:509-527, 1990.
Review of simplex and ellipsoid methods, overview of
combinatorial algorithms, Megiddo's two-dimensional LP algorithm
[Meg83, PS85],
Seidel's randomized incremental algorithm [Sei91],
Matousek-Sharir-Welzl algorithm [MSW96].
Any book on combinatorial optimization (e.g.
[PS82, GLS88, Sch86]) describes
simplex and ellipsoid methods. The survey paper
by Gärtner and Welzl reviews the known combinatorial
algorithms for linear programming in fixed dimensions [PS85].
Matousek et al. [MSW96] describe an abstract
framework, called LP-type problems, and show that their algorithm
extends to any problem that fits in this framework. See
[Ame94, Gär95] for more work on LP-type
problems.
References
- Ame94
-
N. Amenta.
Helly-type theorems and generalized linear programming.
Discrete Comput. Geom., 12:241-261, 1994.
- Gär95
-
Bernd Gärtner.
A subexponential algorithm for abstract optimization problems.
SIAM J. Comput., 24:1018-1035, 1995.
- GLS88
-
M. Grötschel, L. Lovász, and A. Schrijver.
Geometric Algorithms and Combinatorial Optimization, volume 2
of Algorithms and Combinatorics.
Springer-Verlag, Berlin Heidelberg, 1988.
Second edition 1994.
- Meg83
-
N. Megiddo.
Linear-time algorithms for linear programming in
and
related problems.
SIAM J. Comput., 12:759-776, 1983.
- MSW96
-
J. Matousek, M. Sharir, and E. Welzl.
A subexponential bound for linear programming.
Algorithmica, 16:498-516, 1996.
- PS82
-
C. H. Papadimitriou and K. Steiglitz.
Combinatorial Optimization: Algorithms and Complexity.
Prentice Hall, Englewood Cliffs, NJ, 1982.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
- Sch86
-
A. Schrijver.
Theory of Linear and Integer Programming.
Wiley-Interscience, New York, NY, 1986.
- Sei91
-
R. Seidel.
Small-dimensional linear programming and convex hulls made easy.
Discrete Comput. Geom., 6:423-434, 1991.
Clarkson's randomized algorithm [Cla95]; combining
it with Matousek et al. algorithm; LP-type problems.
Selecting the k-th leftmost intersection point;
general paradigm.
Clarkson technique for linear programming has also been applied
to some other geometric optimization problems; see e.g.
[BG95, Cla93, AD97].
The parametric searching was introduced by Megiddo
[Meg79, Meg83]. Optimal algorithms for
computing the k-leftmost intersection point in a set of lines
are presented in
[CSSS89, Mat91, SS93, KS93, BC94].
A survey of techniques used for geometric optimization can be
found in [AS96].
References
- AD97
-
Pankaj K. Agarwal and Pavan K. Desikan.
An approximation algorithm for terrain simplification.
In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pages
139-147, 1997.
- AS96
-
Pankaj K. Agarwal and Micha Sharir.
Efficient algorithms for geoemtric optimization.
Tech. Report CS-1996-19, Dept. Computer Science, Duke University,
1996.
- BC94
-
H. Brönnimann and B. Chazelle.
Optimal slope selection via cuttings.
In Proc. 6th Canad. Conf. Comput. Geom., pages 99-103, 1994.
- BG95
-
H. Brönnimann and M. T. Goodrich.
Almost optimal set covers in finite VC-dimension.
Discrete Comput. Geom., 14:263-279, 1995.
- Cla93
-
Kenneth L. Clarkson.
Algorithms for polytope covering and approximation.
In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of
Lecture Notes Comput. Sci., pages 246-252. Springer-Verlag, 1993.
- Cla95
-
K. L. Clarkson.
Las Vegas algorithms for linear and integer programming.
J. ACM, 42:488-499, 1995.
- CSSS89
-
R. Cole, J. Salowe, W. Steiger, and E. Szemerédi.
An optimal-time algorithm for slope selection.
SIAM J. Comput., 18:792-810, 1989.
- KS93
-
M. J. Katz and M. Sharir.
Optimal slope selection via expanders.
Inform. Process. Lett., 47:115-122, 1993.
- Mat91
-
J. Matousek.
Randomized optimal algorithm for slope selection.
Inform. Process. Lett., 39:183-187, 1991.
- Meg79
-
N. Megiddo.
Combinatorial optimization with rational objective functions.
Math. Oper. Res., 4:414-424, 1979.
- Meg83
-
N. Megiddo.
Applying parallel computation algorithms in the design of serial
algorithms.
J. ACM, 30:852-865, 1983.
- SS93
-
L. Shafer and W. Steiger.
Randomizing optimal geometric algorithms.
In Proc. 5th Canad. Conf. Comput. Geom., pages 133-138, 1993.
Definition, deterministic algorithm for constructing an arrangement,
zone theorem, levels, duality, minimum area triangle in a set
of points.
Most of the material can be found in the book by Edelsbrunner
[Ede87]. The proof of the zone theorem presented in the
class is due to Chazelle et al. [CGL85], and can also be
found in the book by Pach and Agarwal [PA95]. The
paper by Chazelle et al. discusses other applications of
duality and arrangements.
Representation of arrangements in higher dimensions, zone
theorem, lower envelopes, complexity of a single cell,
triangulation. Relationship between lower envelopes and
Davenport-Schinzel sequences.
The material was taken from the book by Sharir and
Agarwal [SA95]. See also the survey paper by Guibas and
Sharir [GS93],
References
- CGL85
-
B. Chazelle, L. J. Guibas, and D. T. Lee.
The power of geometric duality.
BIT, 25:76-90, 1985.
- Ede87
-
H. Edelsbrunner.
Algorithms in Combinatorial Geometry, volume 10 of EATCS
Monographs on Theoretical Computer Science.
Springer-Verlag, Heidelberg, 1987.
- GS93
-
L. Guibas and M. Sharir.
Combinatorics and algorithms of arrangements.
In J. Pach, editor, New Trends in Discrete and Computational
Geometry, volume 10 of Algorithms and Combinatorics, pages 9-36.
Springer-Verlag, 1993.
- PA95
-
Janos Pach and Pankaj K. Agarwal.
Combinatorial Geometry.
John Wiley & Sons, New York, NY, 1995.
- SA95
-
M. Sharir and P. K. Agarwal.
Davenport-Schinzel Sequences and Their Geometric
Applications.
Cambridge University Press, New York, 1995.
General searching problem, semigroup model, range trees,
fractional cascading, lower bounds, improved bounds.
The data structures can be found in the book by Preparata and
Shamos [PS85]. The improved space bound is by
Chazelle [Cha86]. An optimal data structure for
orthogonal range-counting problem was developed by
Chazelle [Cha88]. The lower bounds are proved by
Chazelle in [Cha90a, Cha90b].
Partition trees, ham-sandwich theorem, random sampling,
cuttings, simplicial partition.
The partition tree discussed in the class is by Willard
[Wil82], and the improvement is by Edelsbrunner and
Welzl [EW86]. The lower bound on simplex range
searching is by Chazelle [Cha89]. The best-known
data structure for simplex range searching is by Matousek
[Mat93].
The survey papers by Matousek [Mat94] and
Agarwal [Aga96] summarize most of the results
on simplex range searching and its extensions.
References
- Aga96
-
Pankaj K. Agarwal.
Range searching.
Report CS-1996-05, Dept. Comput. Sci., Duke Univ., Durham, NC, 1996.
- Cha86
-
B. Chazelle.
Filtering search: a new approach to query-answering.
SIAM J. Comput., 15:703-724, 1986.
- Cha88
-
B. Chazelle.
A functional approach to data structures and its use in
multidimensional searching.
SIAM J. Comput., 17:427-462, 1988.
- Cha89
-
B. Chazelle.
Lower bounds on the complexity of polytope range searching.
J. Amer. Math. Soc., 2:637-666, 1989.
- Cha90a
-
B. Chazelle.
Lower bounds for orthogonal range searching, I: the reporting case.
J. ACM, 37:200-212, 1990.
- Cha90b
-
B. Chazelle.
Lower bounds for orthogonal range searching, II: the arithmetic
model.
J. ACM, 37:439-463, 1990.
- EW86
-
H. Edelsbrunner and E. Welzl.
Halfplanar range search in linear space and
query
time.
Inform. Process. Lett., 23:289-293, 1986.
- Mat93
-
J. Matousek.
Range searching with efficient hierarchical cuttings.
Discrete Comput. Geom., 10(2):157-182, 1993.
- Mat94
-
J. Matousek.
Geometric range searching.
ACM Comput. Surv., 26:421-461, 1994.
- PS85
-
F. P. Preparata and M. I. Shamos.
Computational Geometry: An Introduction.
Springer-Verlag, New York, 1985.
- Wil82
-
D. E. Willard.
Polygon retrieval.
SIAM J. Comput., 11:149-165, 1982.
Quad trees, kd-trees, binary space partitions. Applications of
these data structures.
The book by Samet [Sam90] is an excellent source on
quad-trees; the kd-trees were introduced by Bentley
[Ben75]. The binary space partitions were introduced
by Fuchs et al [FKN80] for hidden surface removal.
Since then they have been used for in many problems. The first
nontrivial theoretical bounds on BSP's were proved by Paterson
and Yao [PY90, PY92]. See the paper by
Agarwal et al [AGMV96] and the references therein
for recent work on BSP's.
General set up; multipole
algorithm; other applications of quad trees.
The algorithm for the N-body problem is by Greengard [Gre88]
and can be found in his thesis. A brief overview of his algorithm can
be found in [Gre90].
References
- AGMV96
-
P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter.
Binary space partitions for fat rectangles.
In Proc. 37th Annu. IEEE Sympos. Found. Comput. Sci., October
1996.
- Ben75
-
J. L. Bentley.
Multidimensional binary search trees used for associative searching.
Commun. ACM, 18(9):509-517, 1975.
- FKN80
-
H. Fuchs, Z. M. Kedem, and B. Naylor.
On visible surface generation by a priori tree structures.
Comput. Graph., 14(3):124-133, 1980.
Proc. SIGGRAPH '80.
- Gre88
-
L. Greengard.
The rapid evaluation of potential fields in particle systems.
MIT Press, Cambridge, 1988.
- Gre90
-
L. Greengard.
The numerical solution of the N-body problem.
Computers in Physics, ??:142-152, 1990.
- PY90
-
M. S. Paterson and F. F. Yao.
Efficient binary space partitions for hidden-surface removal and
solid modeling.
Discrete Comput. Geom., 5:485-503, 1990.
- PY92
-
M. S. Paterson and F. F. Yao.
Optimal binary space partitions for orthogonal objects.
J. Algorithms, 13:99-113, 1992.
- Sam90
-
H. Samet.
The Design and Analysis of Spatial Data Structures.
Addison-Wesley, Reading, MA, 1990.
Triangulation with small crossing number [HS95],
visibility-map approach [CG89], multi-level data
structures [Aga92], parametric searching [AM93].
See the survey paper [Aga96].
Visibility map, painter's algorithm, output-sensitive
algorithms, binary space partitions, z-buffer, and volume
rendering.
See the monograph by de Berg [dB93] for known results on
hidden surface removal in computational geometry.
See any book on graphics for graphics algorithms
[FvDF
93].
References
- Aga92
-
Pankaj K. Agarwal.
Ray shooting and other applications of spanning trees with low
stabbing number.
SIAM J. Comput., 21:540-570, 1992.
- Aga96
-
Pankaj K. Agarwal.
Range searching.
Report CS-1996-05, Dept. Comput. Sci., Duke Univ., Durham, NC, 1996.
- AM93
-
Pankaj K. Agarwal and J. Matousek.
Ray shooting and parametric search.
SIAM J. Comput., 22(4):794-806, 1993.
- CG89
-
B. Chazelle and L. J. Guibas.
Visibility and intersection problems in plane geometry.
Discrete Comput. Geom., 4:551-581, 1989.
- dB93
-
M. de Berg.
Ray Shooting, Depth Orders and Hidden Surface Removal, volume
703 of Lecture Notes Comput. Sci.
Springer-Verlag, Berlin, Germany, 1993.
- FvDF
93 -
J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, and Phillips.
Introduction to Computer Graphics.
Addison-Wesley, Reading, MA, 1993.
- HS95
-
J. Hershberger and S. Suri.
A pedestrian approach to ray shooting: Shoot a ray, take a walk.
J. Algorithms, 18:403-431, 1995.
Perturbation methods:
Edelsbrunner-Mücke symbolic perturbation scheme
[Ede87]; improvement by Emiris and Canny [EC91];
a linear perturbation scheme by Seidel [Sei94].
Rounoff errors, issues,
interval arithmetic, floating-point filters, static estimate
of error, exact computation, symbolic-computation methods.
The survey paper by Schirra gives a good overview of all these
topics. See the references in the paper for details.
The book by Hoffman [Hof89] is also an excellent
source.
References
- EC91
-
I. Emiris and J. Canny.
A general approach to removing degeneracies.
In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages
405-413, 1991.
- Ede87
-
H. Edelsbrunner.
Algorithms in Combinatorial Geometry, volume 10 of EATCS
Monographs on Theoretical Computer Science.
Springer-Verlag, Heidelberg, 1987.
- Hof89
-
C. Hoffmann.
Geometric and Solid Modeling.
Morgan-Kaufmann, San Mateo, CA, 1989.
- Sei94
-
R. Seidel.
The nature and meaning of perturbations in geometric computing.
In Proc. 11th Sympos. Theoret. Aspects Comput. Sci., volume 775
of Lecture Notes Comput. Sci., pages 3-17. Springer-Verlag, 1994.
Agarwal's Home Page
Return to
CPS 234 Homepage.
Pankaj Kumar Agarwal
Thu May 1 00:38:34 EDT 1997