Computing shortest transversals of sets (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing shortest transversals of sets (extended abstract)

Full text

Pdf (1.10 MB)

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: 71 - 80

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Binay Bhattacharya	School of Computing Science, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6
Jurek Czyzowicz	Département d'Informatique, Université du Québec à Hull, Hull, Québec, Canada J8X 3X7
Peter Egyed	School of computer Science, McGill University, Montreal, Quebec, Canada H3A 2A7
Ivan Stojmenovic	Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5
Godfried Toussaint	School of computer Science, McGill University, Montreal, Quebec, Canada H3A 2A7
Jorge Urrutia	Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5

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): 5, Downloads (12 Months): 24, 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.109656 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	Mikhail Atallah , Chanderjit Bajaj, Efficient algorithms for common transversals, Information Processing Letters, v.25 n.2, p.87-91, 6 May 1987 [doi>10.1016/0020-0190(87)90226-2]
	2	D. Davis , M. Doskas, Algorithms for high dimensional stabbing problems, Discrete Applied Mathematics, v.27 n.1-2, p.39-48, May 1990 [doi>10.1016/0166-218X(90)90127-X]
	3	D. Avis , J. M. Robert , R. Wenger, Lower bounds for line stabbing, Information Processing Letters, v.33 n.2, p.59-62, Nov. 10, 1989 [doi>10.1016/0020-0190(89)90155-5]
	4	Bajaj, C. and Li, M., 'On the duality of intersection and closest points', Prvc. ~1st Annual Allerlon Conference on Communication and Control, pp. 459-460 (1983).
	5	Bhattacharya, B. K. and Toussaint, G. T., 'Computing shortest transversals', Technical Report TR-SOCS-90.6, McGill University (1990).
	6	Bhattacharya, B. K., Egyed, P. and Toussaint, G. T., 'On computing shortest distances inside X- shaped polygons', manuscript in preparation.
	7	Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
	8	Danzer, L., Griinbaum, B. and Klee, V., 'Helly's theorem and its relatives', In Convexity, Proc. Symposia in Pure Mathematics, American Mathematical Society (1963).
	9	Dyer, M. E., 'Linear time algorithms for two- and three-variable linear programs', SIAM Journal on Computing 13, pp. 31-45 (1984).
	10	H. Edelsbrunner, Computing the extreme distances between two convex polygons, Journal of Algorithms, v.6 n.2, p.213-224, June 1985 [doi>10.1016/0196-6774(85)90039-2]
	11	Edelsbrunner, H., 'Finding transversals for sets of simple geometric figures', Theoretical Computer $czence 35, pp. 55-69 (1985).
	12	H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
	13	Edelsbrunner, E., Guibas, L. J. and Shark, M., 'The upper envelope of piecewise linear functions: algorithms and applications', Discrete and Computational Geometry 4, pp. 311-336 (1989).
	14	Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E. and Wood, D., 'Stabbing line segments', BIT 22, pp. 274-281 (1982).
	15	P. Egyed , R. Wenger, Stabbing pairwise disjoint translates in linear time, Proceedings of the fifth annual symposium on Computational geometry, p.364-369, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73873]
	16	Peter Egyed , Rephael Wenger, Ordered stabbing of pairwise disjoint convex in linear time, Discrete Applied Mathematics, v.31 n.2, p.133-140, 1991 [doi>10.1016/0166-218X(91)90065-5]
	17	Goodman, J. E., Pollack, R. and Wenger, R., 'Geometric Transversal theory', manuscript in preparation.
	18	J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
	19	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
	20	Kiel, M., 'A simple algorithm for determining the envelope of a set of lines', Technical Report 91-1, University of Saskatchewan (1991).
	21	Megiddo, N., 'Linear-time algorithms for linear programming in Ra and related problems', SiAM Journal on Computing 12, pp. 759-776 (1983).
	22	McKenna, M. and Toussaint, G. T., 'Finding the minimum vertex distance between two convex polygons in linear time', Computers and Mathematics with Applications 11, pp. 1227-1242 (1985).
	23	Joseph O'Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM, v.24 n.9, p.574-578, Sept. 1981 [doi>10.1145/358746.358758]
	24	Overmars, M., and van Leeuwen, H., 'Maintenance of configurations in the plane', Journal of Computer and System Sciences 23, pp. 166-204 (1981).
	25	Suri, S., 'Computing the envelope of a set of lines', extended abstract (1985).
	26	Vegter, G., 'Computing the bounded region determined by finitely many lines in the plane', Technical Report CS 8703, University of Groningen (1987).