yoshi_avx's blog

2D function minimum data structure?
By yoshi_avx, history, 58 minutes ago, In English

In my failed attempts at trying to reinvent the Euclidean Closest Pair Problem, I have mostly gotten in the road of trying to check for a list of functions $$$f(x,y)=A\times x+B\times y+C$$$ whether the minimum is larger than a value $$$D$$$ or not.

Can this problem be solved quickly? (For the case $$$C=0$$$, this is just CHT.)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
48 minutes ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

You can let $$$D\to D-C$$$

→ Reply
  • »
    »
    34 minutes ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    C is variable across functions...

    → Reply
    • »
      »
      »
      26 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Oh, sorry, I misunderstood you — you can just binary search on the min and then solve a linear program.

      → Reply
      • »
        »
        »
        »
        21 minute(s) ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        for that problem, I have to do a lot of queries, so $$$O(qn)$$$ wouldn't cut it. Think of the Euclidean closest pair problem.

        → Reply
        • »
          »
          »
          »
          »
          11 minutes ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          If the function set is fixed, just precompute the minimum.

          If a new function is inserted each time, this is a dynamic 2D convex hull — split the hull into an upper hull and a lower hull, and maintain each with a balanced tree or std::set.

          → Reply