CODEWITHSUNDEEP
graphgeometrypolygongraph-theorycomputational-geometry
Desibre93
Desibre93

Reputation: 99

Intersection of polygonal chain with straight line and its complexity

Let Z be an (open or closed) traverse(polygonal chain) in the plane consisting of k line segments. How to edit Z, that for a given query straight line 'g' can be decided quickly (i.e, better than in Θ (k) time) whether g ∩ Z = ∅?

I tried to connect it somehow with some tree structures in order to find any solution...

Upvotes: 0

Views: 74

Answers (1)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

These two papers may help. Although the problem is hard to approximate, if you are willing to accept O( log n ) performance, it is possible.

Chaplick, Steven, Elad Cohen, and Gila Morgenstern. "Stabbing Polygonal Chains with Rays is Hard to Approximate." CCCG. 2013. PDF download.

M.J. Katz, J.S.B. Mitchell, and Y. Nir. Orthogonal segment stabbing. Computational Geometry, 30(2): 197–205, 2005.

Upvotes: 1

Related Questions