Article

Free access

Placing the largest similar copy of a convex polygon among polygonal obstacles

Authors:

L. P. Chew,

K. KedemAuthors Info & Claims

SCG '89: Proceedings of the fifth annual symposium on Computational geometry

Pages 167 - 173

https://doi.org/10.1145/73833.73853

Published: 05 June 1989 Publication History

PDF eReader

Abstract

Given a convex polygon P and an environment consisting of polygonal obstacles, we find the largest similar copy of P that does not intersect any of the obstacles. Allowing translation, rotation, and change-of-size, our method combines a new notion of Delaunay triangulation for points and edges with the well-known functions based on Davenport-Schinzel sequences producing an almost quadratic algorithm for the problem. Namely, if P is a convex k-gon and if Q has n corners and edges then we can find the placement of the largest similar copy of P in the environment Q in time Ο(k⁴n λ₄(kn) log n), where λ₄ is one of the almost-linear functions related to Davenport-Schinzel sequences. If the environment consists only of points then we can find the placement of the largest similar copy of P in time Ο(k²n λ₃(kn) log n).

References

[1]

F. Avnaim and J.D. Boissonnat, Polygon placement under translation and rotation, 5th Annual Symp. on Theoretid Aspects of Computer Science, Lecture Notes in Comp. Science 294, Springer-Verlag, New-York, 1988, pp. 322-333.

Crossref

Google Scholar

[2]

P. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences, to appear in J. Combinatorial Theory, Series A.

Digital Library

Google Scholar

[3]

M. J. Atallah, Dynamic computational geometry, PFOC. 24th IE:Eld Symp. on Foundations of Computrr Science, 1983, pp. 92-99.

Digital Library

Google Scholar

[4]

L.P. Chew and R.L. Drysdale, Voronoi diagrams based on convex distance functions, PFOC. ACM S.ymposium on Computational Geometry, 1985, pp. 235-244.

Digital Library

Google Scholar

[5]

B. Chazelle, The polygon containment problem, in Advances in Computing Research, Vol. I: Computational Geometry, (F.P. Preparata, Ed.), JAI Press, Greenwich, Conneticut (19831, pp. l-33.

Google Scholar

[6]

L.P. Chew, Constrained Delaunay Triangulations, to appear in Algorithmica.

Google Scholar

[7]

S. Fortune, Fast algorithms for polygon containment, Proc. 12th InteF- national Colloquium on Automata, Language and Programming, Lecture Notes in Comp. Science 194, Springer- Verlag, New-York, 1985, pp. 189-198.

Digital Library

Google Scholar

[8]

S. Fortune, A sweepline algorithm for Voronoi diagrams, Algorithmica, 2 (1987), pp. 153-174.

Digital Library

Google Scholar

[9]

K. Kedem and M. Sharir, An efficient motion planning algorithm for a convex polygonal object in 2-dimensional space, to appear in Discrete and Cornputational Geometry, 1988.

Google Scholar

[10]

D.T. Lee and A.K. Lin, Generalized Delaunay Triangulation for Planar Graphs, Discrete ad Computational Geometry, 1 (1986), pp, 201-217.

Google Scholar

[11]

D. Leven and M. Sharir, Planning a purely translational motion for a convex polygonal object in two dimensional space using Generalized Voronoi diagrams, Discrete and Computational Geometry, 2 (19871, pp. 255-270.

Digital Library

Google Scholar

[12]

M. Sharir, R. Cole, K. Kedem, D. Leven, R. Pollack and S. Sifrony, Geometric applications of Davenport- Schinzel sequences, Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 77-86.

Digital Library

Google Scholar

[13]

C.K. Yap, An O(n logn) algorithm for the Voronoi diagram of a set of simple curve segments, Discrete and Computational Geometry, 2 (19871, pp. 365-393.

Digital Library

Google Scholar

Cited By

View all

Kowaluk MMajewska G(2015)$$\beta $$-skeletons for a Set of Line Segments in $$R^2 $$Fundamentals of Computation Theory10.1007/978-3-319-22177-9_6(65-78)Online publication date: 4-Aug-2015
https://doi.org/10.1007/978-3-319-22177-9_6
Memari PBoissonnat JAlliez PRusinkiewicz S(2008)Provably good 2D shape reconstruction from unorganized cross-sectionsProceedings of the Symposium on Geometry Processing10.5555/1731309.1731323(1403-1410)Online publication date: 2-Jul-2008
https://dl.acm.org/doi/10.5555/1731309.1731323
Memari PBoissonnat J(2008)Provably Good 2D Shape Reconstruction from Unorganized Cross‐SectionsComputer Graphics Forum10.1111/j.1467-8659.2008.01280.x27:5(1403-1410)Online publication date: 29-Sep-2008
https://doi.org/10.1111/j.1467-8659.2008.01280.x
Show More Cited By

Index Terms

Placing the largest similar copy of a convex polygon among polygonal obstacles
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Probability and statistics
    1. Statistical paradigms
      1. Queueing theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Placing the Largest Similar Copy of a Convex Polygon Among Polygonal Obstacles
Visibility Polygon Queries Among Dynamic Polygonal Obstacles in Plane
Computing and Combinatorics
Abstract
Given a polygonal domain, we devise a fully dynamic algorithm for maintaining the visibility polygon of any query point, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the visibility ...
Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
Abstract
We devise an algorithm for maintaining the visibility polygon of any query point in a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the data structures that ... $_{^{}} {^{}}^{}$ ${^{}}^{}_{^{}}$ $_{^{}}$ $^{}$ $^{}$ $^{}$ $^{}$ $_{^{}}$ $^{}$ $_{^{}}$ $_{^{}}$ $_{^{}}$ ${^{}}^{}$ ${^{}}^{}$ $^{}$ $^{}$ $^{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '89: Proceedings of the fifth annual symposium on Computational geometry

June 1989

401 pages

ISBN:0897913183

DOI:10.1145/73833

Chairman:
Kurt Mehlhorn

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
422
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)12

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kowaluk MMajewska G(2015)$$\beta $$-skeletons for a Set of Line Segments in $$R^2 $$Fundamentals of Computation Theory10.1007/978-3-319-22177-9_6(65-78)Online publication date: 4-Aug-2015
https://doi.org/10.1007/978-3-319-22177-9_6
Memari PBoissonnat JAlliez PRusinkiewicz S(2008)Provably good 2D shape reconstruction from unorganized cross-sectionsProceedings of the Symposium on Geometry Processing10.5555/1731309.1731323(1403-1410)Online publication date: 2-Jul-2008
https://dl.acm.org/doi/10.5555/1731309.1731323
Memari PBoissonnat J(2008)Provably Good 2D Shape Reconstruction from Unorganized Cross‐SectionsComputer Graphics Forum10.1111/j.1467-8659.2008.01280.x27:5(1403-1410)Online publication date: 29-Sep-2008
https://doi.org/10.1111/j.1467-8659.2008.01280.x
Brévilliers MChevallier NSchmitt D(2008)Flip Algorithm for Segment TriangulationsProceedings of the 33rd international symposium on Mathematical Foundations of Computer Science10.1007/978-3-540-85238-4_14(180-192)Online publication date: 25-Aug-2008
https://dl.acm.org/doi/10.1007/978-3-540-85238-4_14
Brévilliers MChevallier NSchmitt D(2007)Triangulations of line segment sets in the planeProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781828(388-399)Online publication date: 12-Dec-2007
https://dl.acm.org/doi/10.5555/1781794.1781828
Brévilliers MChevallier NSchmitt D(2007)Triangulations of Line Segment Sets in the PlaneFSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science10.1007/978-3-540-77050-3_32(388-399)Online publication date: 2007
https://doi.org/10.1007/978-3-540-77050-3_32
Fleischer RFries OMehlhorn KMeiser SNäher SRohnert HSchirra SSimon KTsakalidis AUhrig C(2005)Selected topics from computational geometry, data structures and motion planningData structures and efficient algorithms10.1007/3-540-55488-2_20(25-43)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-55488-2_20
Halperin DSharir M(1993)Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environmentProceedings of the 1993 IEEE 34th Annual Foundations of Computer Science10.1109/SFCS.1993.366849(382-391)Online publication date: 3-Nov-1993
https://dl.acm.org/doi/10.1109/SFCS.1993.366849
Chew LKedem K(1993)A convex polygon among polygonal obstaclesComputational Geometry: Theory and Applications10.1016/0925-7721(93)90001-M3:2(59-89)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1016/0925-7721%2893%2990001-M
Mount DAvis D(1992)Intersection detection and separators for simple polygonsProceedings of the eighth annual symposium on Computational geometry10.1145/142675.142737(303-311)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/142675.142737
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Placing the Largest Similar Copy of a Convex Polygon Among Polygonal Obstacles

Visibility Polygon Queries Among Dynamic Polygonal Obstacles in Plane

Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane