1
$\begingroup$

There is a nice decomposition called trapezoidal to process point location queries given a set of disjoint generally curvilinear segments. I found the randomized algorithm for building this type of decomposition in Berg's book on computational geometry. Can someone point me out papers which report deterministic algorithms with only a little polynomial overhead which provides the same capabilities of trapezoidal decomposition for point location ?

$\endgroup$
  • $\begingroup$ I believe that finding an efficient algorithm for trapezoidal decomposition is an open and important question within the field. Trapezoidal decomposition is an important technique for many algorithms and has an algorithm that works a lot better in theory than in practice. So finding an algorithm that works in practice means that a lot 'theoretical' algorithms might become practical. So, I believe the answer to your question would be 'no', at least for now. $\endgroup$ – Discrete lizard Feb 14 '17 at 8:40
0
$\begingroup$

I finally found recent paper titled "Optimal randomized incremental construction for guaranteed logarithmic planar point location" by several authors, where deterministic times are given for query and the seach structure, but expected time for preprocessing.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.