5
$\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$
5
  • $\begingroup$ You refer to a query point, but I don't see any query point in the statement of the problem. $\endgroup$
    – D.W.
    Commented Mar 21, 2020 at 16:03
  • $\begingroup$ Line segments in $\Bbb R^2$? $\endgroup$ Commented Mar 21, 2020 at 19:47
  • $\begingroup$ Did you have a look at cs.stackexchange.com/questions/120384/… (if you consider your line a 'shape') and cs.stackexchange.com/questions/117333/… (if you consider lines as bounding boxes). $\endgroup$
    – TilmannZ
    Commented Mar 22, 2020 at 14:05
  • $\begingroup$ Please also see my answer here: cs.stackexchange.com/questions/123349/… $\endgroup$
    – HEKTO
    Commented Jun 2, 2020 at 21:53
  • $\begingroup$ The duals of the line segments are those wedges and the dual of the line is a single point. So you have to construct the arrangement of lines generated by the wedges and from this, point location in that planar subdivision. Nothing really appetizing... $\endgroup$
    – user16034
    Commented Jun 27, 2023 at 14:39

1 Answer 1

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$
5
  • 1
    $\begingroup$ Are you the one who asked the original question? $\endgroup$ Commented Apr 1, 2021 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$ Commented Apr 1, 2021 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.
    Commented Apr 1, 2021 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
    Commented Apr 15, 2021 at 0:50
  • 1
    $\begingroup$ I upvoted as this seems to be a useful partial answer. According to the teacher part (a) and (b) are correct and part (c) is incorrect. $\endgroup$ Commented Feb 23 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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