Optimal algorithms for some smallest intersection radius problems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal algorithms for some smallest intersection radius problems (extended abstract)

Full text

Pdf (533 KB)

Source

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

North Conway, New Hampshire, United States

Pages: 81 - 88

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Binay K. Bhattacharya	School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada, V5A 1S6
Sreesh Jadhav	Department of Computer Science, Indian Institute of Technology, Kanpur, India
Asish Mukhopadhayay	Department of Computer Science, Indian Institute of Technology, Kanpur, India
Jean-Marc Robert	School of Computer Science, McGill University, 3480 University St., Montreal, P.Q., Canada, H3A 2A7

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): 11, Downloads (12 Months): 34, Citation Count: 1

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/109648.109657 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.

	Bhattacharya90a	Bhattacharya, B.K. and Toussaint, G.T., "Computing shortest transversals," Tech. Report SOCS 90.6, McGill University, April 1990.
	Bhattacharya90b	Bhattacharya, B.K., Czyzowicz, J., Egyed, P., Toussaint, G., Stojmenovic, I. and Urrutia, J., "Computing shortest transversals of sets," Manuscript in preparation, 1990.
	Brown78	Brown, K.Q., "Fast intersection of half spaces," Carnegie-Mellon University, Pittsburg, Department of Computer Science, Report CMU-CS-78-129, 1978.
	Clarkson86	K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
	Chrystal85	Chrystal, G., "On the problem to construct the minimum circle enclosing n given points in the plane," Proc. Edinburgh Math. Soc., Vol.3, pp.30-33, 1885.
	Dyer84	Dyer, M.E., "Linear-time algorithm for two- and three-variable linear programs," SIAM J. Computing, Vol. 13, pp.31-45, 1984.
	Dyer86	M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
	Goodrich89	Michael T. Goodrich , Jack Snoeyink, Stabbing Parallel Segments with a Convex Polygon (Extended Abstract), Proceedings of the Workshop on Algorithms and Data Structures, p.231-242, August 17-19, 1989
	Hadwiger64	Hadwiger,H, Debrunner, H. and Klee, V., Combinatorial geometry in the plane, Holt, Rinehart and Winston, 1964.
	Houle89	Michael E. Houle , Hiroshi Imai , Keiko Imai , Jean-Marc Robert, Weighted Orthogonal Linear L\infty-Approximation and Applications, Proceedings of the Workshop on Algorithms and Data Structures, p.183-193, August 17-19, 1989
	Megiddo83	Megiddo, N., "Linear-time algorithms for linear programming in R3 and related problems,'' SIAM J. Computing, Vol. 12, pp.759-776, 1983.
	Megiddo84	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	Shamos78	Michael Ian Shamos, Computational geometry., 1978
	Seidel90	Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
	Sylvester57	Sylvester, J.J., "A question in the geometry situation," Quart. J. Pure Appl. Math., Vol. 1, pp.79, 1857.
	Sylvester60	Sylvester, J.J., "On Poncelet's approximate linear valuation of surd forms," Philosophical Magazine, Vol.20, (fourth series), pp.203-222, 1860.