Chasty's blog

What is coordinate compression?
By Chasty, history, 10 years ago, In English

Hi all. Could some please make me understand what it is with an example? I'll appreciate it. DO you have some problems to apply it?

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

Comments Comments (12)
| Write comment?
»
7 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

In Chinese: 离散化(ie. map larger values to smaller distinct values)

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

please explain cordinate compression someone i can't solve a problem relating to this please help me

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Let's say that in a problem, you're required to store N (1 <= N <= 10^5) elements and perform some operations on those elements (say put them in a Segment Tree). Normally, if the elements were also in the range (1, 10^5), inserting them into a data structure would be a cinch.

Say, for example, the elements are now in the range (1, 10^12). Now simply inserting elements into a Segment Tree is not possible because you cannot allocate memory for 10^12 integers. This is where coordinate compression comes into play.

Let's read in all of the possible numbers, sort them, and assign each of them a number based off of increasing order. Because N is <= 10^5, the maximum number you assign is going to be 10^5. Thus, by compressing the "coordinates", we maintain the relative order of points in a memory-efficient manner.

I hope this helps!

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Good problem http://usaco.org/index.php?cpid=207&page=viewproblem2

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

It's when you take some coordinates, put them all in a hydraulic press. Then they become "compressed".

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

Check this video out.

→ Reply