Header menu link for other important links
Intersection removal for simple polygons
Kamala Krithivasan
Published in Taylor and Francis Inc.
Volume: 64
Issue: 3-4
Pages: 211 - 223
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.
Open AccessNo
Concepts (5)
  •  related image
  •  related image
    Computational complexity
  •  related image
    Problem solving
  •  related image
  •  related image
    Computational geometry