3
$\begingroup$

We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries: Given a query line $l$, report how many line segments in $S$ does it intersect.

It is required that the query should be done in $O(\log{n})$ time. The data structure itself should take up to $O(n^{2})$ storage and be built in $O(n^{2}\log{n})$ time. It is suggested that it should be done in dual plane.

I understand that the question may require me to look for the number of double wedge that the a query point is in, but I can't think of any efficient data structure to report such information. Any suggestions?

This question is basically a homework question from the textbook Computational Geometry by de Berg et al (Question 8.15). I would like to apologize that this question may not be exciting to you.

Edit: Yes it is in $\mathbb{R}^{2}$. By query point I mean the query line dualised into a point on dual plane.

$\endgroup$
4
-1
$\begingroup$

HERE is the solution I did in the homework but it still lose three points on:

(3 points) Construct the O(n^2) faces with proper intersection counts of each faces.

enter image description here

enter image description here

enter image description here

$\endgroup$
4
  • 1
    $\begingroup$ Are you the one who asked the original question? $\endgroup$ – Yuval Filmus Apr 1 at 16:15
  • 2
    $\begingroup$ It is a bit problematic to add an answer which you know is (slightly) wrong, without at least pointing out potential problems in it. $\endgroup$ – Yuval Filmus Apr 1 at 16:15
  • 1
    $\begingroup$ We'd prefer that you not use images as main content of your post. This makes your answer impossible to search and inaccessible to the visually impaired; we don't like that. It would be better to transcribe text and mathematics. You can use LaTeX. $\endgroup$ – D.W. Apr 1 at 18:48
  • $\begingroup$ 1. No, I'm not the one who asks the question 2. for image since I use the color to correspond to figure information, I don't think it's convienet for me to transcribe text, or you can do it, and I will delete the answer if someone transcribes to txt 3. All answers are not perfect, and I think I point out why it's didn't totally right, I think others can just see it as reference but not the correct answer. $\endgroup$ – Zhang Kin Apr 15 at 0:50

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.