On levels in arrangements of lines, segments, planes, and triangles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On levels in arrangements of lines, segments, planes, and triangles

Full text

Pdf (1.18 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 30 - 38

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Pankaj K. Agarwal	Department of Computer Science, Box 90129, Duke University, Durham, NC
Boris Aronov	Department of Computer and Information Science, Polytechnic University, Brooklyn, NY
Micha Sharir	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.262856 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N Alon , E Györi, The number of small semispaces of a finite set of points in the plane, Journal of Combinatorial Theory Series A, v.41 n.1, p.154-157, Jan. 1986 [doi>10.1016/0097-3165(86)90122-6]
	2	Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991 [doi>10.1007/BF02574700]
	3	I. B~r~ny, Z. Ffiredi, and L. Lov#sz, On the number of halving planes, Cornbinatorica 10 (1990), 175-183.
	4	I. B&rgny and W. Steiger, On the expected number of k-sets, Discrete Cornput. Geom. 11 (1994), 243-263.
	5	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , John E. Hershberger , Raimund Seidel , Micha Sharir, Selecting Heavily Covered Points, SIAM Journal on Computing, v.23 n.6, p.1138-1151, Dec. 1994 [doi>10.1137/S0097539790179919]
	6	K. Clarkson, A bound on local minima of arrangements that implies the Upper Bound Theorem, Discrete Cornput. Geom. 10 (1993), 427-433.
	7	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	8	T. Dey and H. Edelsbrunner, Counting triangle crossings and halving planes, Discrete Cornput. Geom. 12 (1994), 281-289.
	9	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	10	Herbert Edelsbrunner , Pavel Valtr , Emo Welzl, Cutting dense point sets in half, Proceedings of the tenth annual symposium on Computational geometry, p.203-209, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177648]
	11	P. ErdSs, L. Lov#sz, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, In J. N. Srivastara et M., editors, A Survey of Combinatorial Theory, North-Holland, Amsterdam, 1973, pp. 139-149.
	12	J. E. Goodman and R. Pollack, Allowable Sequences and Order Types in Discrete and Computational Geometry, in New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics (J. Pach, Ed.), vol. 10, Springer-Verlag, 1993, 103-134.
	13	Daniel Mier Gusfield, Sensitivity analysis for combinatorial optimization, 1980
	14	D. Gusfield, Bounds for the parametric minimum spanning tree problem, Proc. Humboldt Conference on Graph Theory, Cornbinatorics and Computing, 1979, Utilitas Mathematica, pp. 173-183.
	15	Dan Halperin , Micha Sharir, On disjoint concave chains in arrangements of (pseudo) lines, Information Processing Letters, v.51 n.1, p.53-56, July 12, 1994 [doi>10.1016/0020-0190(94)00057-3]
	16	Dan Halperin , Micha Sharir, On disjoint concave chains in arrangements of (pseudo) lines, Information Processing Letters, v.51 n.1, p.53-56, July 12, 1994 [doi>10.1016/0020-0190(94)00057-3]
	17	John Hershberger , Jack Snoeyink, Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.376-387, July 08-10, 1992
	18	M. Klawe, M. Paterson, and N. Pippenger, unpublished manuscript.
	19	L. LovAsz, On the number of halving lines, Ann. Univ. Sci. Budapest, EStvSs, Sec. Math. 14 (1971), 107-108.
	20	Janos Pach , K P Agarwal, Combinatorial Geometry, Duke University, Durham, NC, 1991
	21	János Pach , William Steiger , Endre Szemerédi, An upper bound on the number of planar K-sets, Discrete & Computational Geometry, v.7 n.2, p.109-123, 1992 [doi>10.1007/BF02187829]
	22	M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Coraput. Geom. 6 (1991), 593-613.
	23	Hisao Tamaki , Takeshi Tokuyama, How to cut pseudo-parabolas into segments, Proceedings of the eleventh annual symposium on Computational geometry, p.230-237, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220304]
	24	Emo Welzl, More on k-sets of finite sets in the plane, Discrete & Computational Geometry, v.1 n.1, p.95-100, 1986 [doi>10.1007/BF02187686]
	25	Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]
	26	Rade T. Živaljevic , Sinša T. Vrecica, The colored Tverberg's problem and complexes of injective functions, Journal of Combinatorial Theory Series A, v.61 n.2, p.309-318, Nov. 1992 [doi>10.1016/0097-3165(92)90028-S]

CITED BY 4

	Artur Andrzejak , Boris Aronov , Sariel Har-Peled , Raimund Seidel , Emo Welzl, Results on k-sets and j-facets via continuous motion, Proceedings of the fourteenth annual symposium on Computational geometry, p.192-199, June 07-10, 1998, Minneapolis, Minnesota, United States
	Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Parametric polymatroid optimization and its geometric applications, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.517-526, January 17-19, 1999, Baltimore, Maryland, United States
	Helmut Alt , Stefan Felsner , Ferran Hurtado , Marc Noy, Point-sets with few k-sets, Proceedings of the fourteenth annual symposium on Computational geometry, p.200-205, June 07-10, 1998, Minneapolis, Minnesota, United States
	Timothy M. Chan, On levels in arrangements of curves, iii: further improvements, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA