I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside of the rectangles that define the constraints. I want to be able to find if an edge lies inside of a rectangle in O(1) time.

Here's a more general description of the problem I want to solve. Given a set of nonoverlapping rectangles (the borders of the rectangles may touch) and an edge e with endpoints (x1,y1) and (x2, y2), find in O(1) time if e lies within any of the rectangles (including the border).

  • $\begingroup$ Not possible. Just deciding whether a point lies inside one of the rectangles requires $\Omega(\log n)$ time, even if the rectangles are disjoint unit squares resting on the x-axis. $\endgroup$ – Jeffε Feb 11 '14 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.