misael's blog

Find the leftmost intersection of lines?
By misael, history, 7 years ago, In English

Given N <= 10^5 lines, how to find the leftmost intersection of two lines?

Obs : Lines are in the Cartesian Plane

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I believe this should work: Go to the dual space. Now you need to find a line going through two of the points that is closest to vertical. This will be one of the pairs of points that are consecutive in x direction. Sketch of proof: assume that a non-consecutive pair (A,B) of points is better and point C between them, one of the pairs (A,C) or (B,C) will be better.

We probably don't need dual space because the rest of solution is equivalent to taking lines with consecutive slopes, but the proof gets less intuitive then.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain this part? "Now you need to find a line going through two of the points that is closest to vertical."

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If we take equivalence (point a,b) <-> (line y=ax+b) then the leftmost point is equivalent to line with minimal slope. I assumed that there exists a line with a<0 then it looks like that \ and more vertical ones have lower slopes. I forgot that there can be no such line, in that case we have a>=0 and the lowest slope will be the line closest to horizontal. You need to check both conditions.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Could you explain what dual space is, please? I've only found some weird Wikipedia articles for mathematicians :(

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          In a very general picture, we have two types of objects (not necessarily the same) and we define some kind of equivalence between them such that some desired properties are conserved.

          A common one is to pair point a,b with line y=ax+b. Notice that dual(dual(a,b))=a,b. For a picture of a bit different point-line duality relation see here.

          We have a useful property that if point p lies on line l then point dual(l) lies on line dual(p). This means that any geometry problem that relies only on points, lines and intersections (e.g. no distances are involved) can be transformed into a dual one, that is possibly easier to solve.

          In the current case, we have a set of lines and are interested in their intersections. We transform each line into a point and notice that intersection point of lines k and l transforms into a line passing through dual(k) and dual(l).

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you very much. One more question — what happens with lines parallel to OY?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              AFAIK, it doesn't happen. You have to rotate or translate the plane usually to be able to use duality, depending on its kind (I knew the one with ax + by + 1 = 0 -> (a, b) where translation is more useful)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yeah, the Wikipedia picture I linked to contains exactly this one. But in the current case I couldn't find any nice indicator of ax+by=1 with a=min and with y=ax+b it is easier.

                → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by misael (previous revision, new revision, compare).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way, if you apply the most standard algorithm of checking whether any two of the lines intersect (the set one described in Cormen's book), you might accidentally find the leftmost intersection. Correct me if I'm wrong, I'm not sure about it.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

i think we can do binary search on answer, we need to check if there is any intersection with x ≤ mid , so draw a line x = mid and then see intersection of all given lines with this line , now suppose a line with slope m intersects x = mid at some y , then this intersects with some other given line on the left of x = mid if there is another line which intersects x = mid at some y' > y and has slope m' > m. or has y' < y and m' < m
Can someone confirm if this works?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think this work. If put all (y, m) in a vector<> and then sort, the only way that doesn't exist intersection to the left of mid is if the m's in this vector are in descending order.

    → Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Say line f(x) = ax + b. sort by decreasing order of a (which is f(-inf)), now answer is one of the adjacent lines in that sorted list.

This will be effectively same as ania's algorithm, I think.

→ Reply