Header menu link for other important links
X
Intersection removal for simple polygons
Kamala Krithivasan
Published in Taylor and Francis Inc.
1997
Volume: 64
   
Issue: 3-4
Pages: 211 - 223
Abstract
Given two intersecting simple polygons A and B and a direction, θ, we have to find the minimum distance by which B should be translated along direction θ so that A and B no longer intersect. We present two algorithms for this problem for the case that A and B are in 2 dimensions and one algorithm for the case that they are in 3 dimensions. The 2 dimensional algorithms run in script O sign(N4) and script O sign(N3 log N) time respectively where N is the total number of vertices in both the polygons while the 3 dimensional algorithm runs in script O sign(N4) time.
About the journal
JournalData powered by TypesetInternational Journal of Computer Mathematics
PublisherData powered by TypesetTaylor and Francis Inc.
ISSN00207160
Open AccessNo
Concepts (5)
  •  related image
    Algorithms
  •  related image
    Computational complexity
  •  related image
    Problem solving
  •  related image
    INTERSECTION REMOVAL
  •  related image
    Computational geometry