CPS 234: Summary of Lectures

Pankaj K. Agarwal


January 16, 1997

 

Models of computation:

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 tex2html_wrap_inline155 time; a matching lower bound is proved by Chazelle and Rosenberg [CR89].

Lower bounds:

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.

January 21, 1997

 

Basic data structures:

Segment trees [PS85, Section 1.2.3,], interval trees [PS85, Section-8.2,], priority search trees [McC85, IKO88]; interval queries, ground rectangle queries;

Segment intersection:

Intersection reporting, naive algorithm, line sweep [BO79, Bro81]; intersection counting.

The best known algorithm for segment-intersection counting runs in time roughly tex2html_wrap_inline159 [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.

January 28, 1997

 

Segment intersection:

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].

Planar convex hulls

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 tex2html_wrap_inline112 -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.

February 4, 1997

 

Convex polytopes

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].

Convex hulls in higher dimensions

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.

February 11, 1997

 

Convex hulls

A randomized incremental algorithm for computing the convex hull of a set of points in d-space with expected running time tex2html_wrap_inline274 . 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.

February 27, 1997

 

Segment intersection

A randomized incremental algorithm, with tex2html_wrap_inline276 expected time, for reporting all k intersection points in a set of n segments. Such algorithms are described in [CS89, Mul90, Mul91, CEG tex2html_wrap_inline282 93]. Deterministic algorithms with the same time are presented in [CE92, Bal95].

Diameter, width

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 tex2html_wrap_inline282 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 tex2html_wrap_inline286 . Computat. Geom. Theory Appl., 6:in press, 1996.

March 4, 1997

 

Voronoi diagram

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 tex2html_wrap_inline390 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 tex2html_wrap_inline282 95, CKS tex2html_wrap_inline282 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 tex2html_wrap_inline282 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.

March 6, 1997

 

Planar point location: Persistent data structure

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.

Point location: Monotone chain method

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.

March 25, 1997

 

Linear programming

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 tex2html_wrap_inline286 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.

April 1, 1997

 

Linear programming

Clarkson's randomized algorithm [Cla95]; combining it with Matousek et al. algorithm; LP-type problems.

Parametric searching

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.

April 8, 1997

 

Arrangements of lines

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.

Arrangement of hyperplanes and surfaces

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.

April 10, 1997

 

Orthogonal range searching

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].

Simplex range searching

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 tex2html_wrap_inline591 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.

April 15, 1997

 

Practical data structures

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.

N-body problem

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.

April 22, 1997

Ray shooting

Triangulation with small crossing number [HS95], visibility-map approach [CG89], multi-level data structures [Aga92], parametric searching [AM93]. See the survey paper [Aga96].

Hidden surface removal

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 tex2html_wrap_inline282 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 tex2html_wrap_inline282 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.

April 29, 1997

Degeneracies

Perturbation methods: Edelsbrunner-Mücke symbolic perturbation scheme [Ede87]; improvement by Emiris and Canny [EC91]; a linear perturbation scheme by Seidel [Sei94].

Robustness issues:

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