Thick non-crossing paths and minimum-cost flows in polygonal domains

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Thick non-crossing paths and minimum-cost flows in polygonal domains

Full text

Pdf (513 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-third annual symposium on Computational geometry table of contents

Gyeongju, South Korea

SESSION: Session 2 table of contents

Pages: 56 - 65

Year of Publication: 2007

ISBN:978-1-59593-705-6

Authors

Valentin Polishchuk	Helsinki Institute for Information Technology, Helsinki, Finland
Joseph S.B. Mitchell	Stony Brook University, Stony Brook, NY

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, 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/1247069.1247079 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	[1] P. K. Agarwal and M. Sharir. Arrangements and their applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 49-119. Elsevier Science B.V. North-Holland, Amsterdam, 2000.
	2	A Aggarwal , M Klawe , S Moran , P Shor , R Wilber, Geometric applications of a matrix searching algorithm, Proceedings of the second annual symposium on Computational geometry, p.285-292, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10546]
	3	[3] O. Bastert and S. P. Fekete. Geometric wire routing. Technical Report 332, Zentrum für Angewandte Informatik, 1998.
	4	Sergei Bespamyatnikh, Computing homotopic shortest paths in the plane, Journal of Algorithms, v.49 n.2, p.284-303, November 2003 [doi>10.1016/S0196-6774(03)00090-7]
	5	[5] S. Bespamyatnikh. Encoding homotopy of paths in the plane. In Proc. LATIN '04, LNCS 2976, pages 329-338, 2004.
	6	Sergio Cabello , Yuanxin Liu , Andrea Mantler , Jack Snoeyink, Testing Homotopy for paths in the plane, Proceedings of the eighteenth annual symposium on Computational geometry, p.160-169, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513421]
	7	[7] F. Chin, J. Snoeyink, and C. A. Wang. Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom., 21(3):405-420, 1999.
	8	[8] R. Cole and A. Siegel. River routing every which way, but loose. In Proc. 25th Annu. IEEE Sympos. Found. Comput. Sci., pages 65-73, 1984.
	9	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	10	A. Efrat , S. Kobourov , M. Stepp , C. Wenk, Growing fat graphs, Proceedings of the eighteenth annual symposium on Computational geometry, p.277-278, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513434]
	11	Alon Efrat , Stephen G. Kobourov , Anna Lubiw, Computing Homotopic Shortest Paths Efficiently, Proceedings of the 10th Annual European Symposium on Algorithms, p.411-423, September 17-21, 2002
	12	S. Gao , M. Jerrum , M. Kaufman , K. Mehlhorn , W. Rülling, On continuous Homotopic one layer routing, Proceedings of the fourth annual symposium on Computational geometry, p.392-402, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73433]
	13	L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
	14	John Hershberger , Jack Snoeyink, Computing minimum length paths of a given homotopy class, Computational Geometry: Theory and Applications, v.4 n.2, p.63-97, June 1994 [doi>10.1016/0925-7721(94)90010-8]
	15	[15] S. Hirsch and E. Leiserowitz. Exact construction of minkowski sums of polygons and a disc with application to motion planning. Technical report ECG-TR181205-01, Tel-Aviv University, 2002.
	16	H. van der Holst , J. C. de Pina, Length-bounded disjoint paths in planar graphs, Discrete Applied Mathematics, v.120 n.1-3, p.251-261, 15 August 2002 [doi>10.1016/S0166-218X(01)00294-3]
	17	Chi-Ping Hsu, General river routing algorithm, Proceedings of the 20th conference on Design automation, p.578-583, June 27-29, 1983, Miami Beach, Florida, United States
	18	Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
	19	Yoshiyuki Kusakari , Hitoshi Suzuki , Takao Nishizeki, Finding a Shortest Pair of Paths on the Plane with Obstacles and Crossing Areas, Proceedings of the 6th International Symposium on Algorithms and Computation, p.42-51, December 04-06, 1995
	20	D. T. Lee , C. D. Yang , C. K. Wong, Rectilinear paths among rectilinear obstacles, Discrete Applied Mathematics, v.70 n.3, p.185-215, Oct. 8, 1996 [doi>10.1016/0166-218X(96)80467-7]
	21	C E Leiserson , F M Maley, Algorithms for routing and testing routability of planar VLSI layouts, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.69-78, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22153]
	22	F. Miller Malley, Single-layer wire routing and compaction, MIT Press, Cambridge, MA, 1990
	23	Elefterios A. Melissaratos , Diane L. Souvaine, On solving geometric optimization problems using shortest paths, Proceedings of the sixth annual symposium on Computational geometry, p.350-359, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98600]
	24	Joseph S. B. Mitchell, On maximum flows in polyhedral domains, Journal of Computer and System Sciences, v.40 n.1, p.88-123, February 1990 [doi>10.1016/0022-0000(90)90020-L]
	25	[25] J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633-701. Elsevier Science B.V. North-Holland, Amsterdam, 2000.
	26	[26] V. Polishchuk. Thick Non-Crossing Paths and Minimum-Cost Continuous Flows in Geometric Domains. PhD thesis. Stony Brook University, 2007.
	27	[27] E. Papadopoulou. Personal communication.
	28	[28] E. Papadopoulou. k-pairs non-crossing shortest paths in a simple polygon. Int. J. Comp. Geom. Appl., 9(6):533-552, 1999.
	29	[29] G. Strang. Maximal flow through a domain. Math. Program., 26:123-143, 1983.
	30	Jun-ya Takahashi , Hitoshi Suzuki , Takao Nishizeki, Finding Shortest Non-Crossing Rectilinear Paths in Plane Regions, Proceedings of the 4th International Symposium on Algorithms and Computation, p.98-107, December 15-17, 1993
	31	[31] C. D. Yang, D. T. Lee, and C. K. Wong. On bends and lengths of rectilinear paths: a graph theoretic approach. Internat. J. Comput. Geom. Appl., 2(1):61-74, 1992.