Sunday, October 23, 2011

Acrobat: The crop page pop-up menu in Acrobat X tools

In the latest version of Acrobat professional readers,
Clicking on Tools > Pages > Crop only shows manual rectangle crop selection. 
There is no pop-up menu showing me options such as "removed white margins" etc as in older versions.

The way to crop pages is to  make a rectangle with the crop tool, 
then double-click there is an check-box to remove white margins, similar to older versions.


Wednesday, October 19, 2011

Latex: how to number your equation at any line

1. Number each line

D_{o_1o_2}&(t) =  ((v_{x_1}-v_{x_2})^2+(v_{y_1}-v_{y_2})^2) \cdot t^2
\\  & + \left( (x_1-x_2)(v_{x_1}-v_{x_2})+(y_1-y_2)(v_{y_1}-v_{y_2}) \right )\cdot 2t
\\  & +(x_1-x_2)^2+(y_1-y_2)^2

2. Number one line

\notag D_{o_1o_2}&(t) =  ((v_{x_1}-v_{x_2})^2+(v_{y_1}-v_{y_2})^2) \cdot t^2
\notag \\  & + \left( (x_1-x_2)(v_{x_1}-v_{x_2})+(y_1-y_2)(v_{y_1}-v_{y_2}) \right )\cdot 2t
\notag \\  & +(x_1-x_2)^2+(y_1-y_2)^2

3. No numbering

 D_{o_1o_2}&(t) =  ((v_{x_1}-v_{x_2})^2+(v_{y_1}-v_{y_2})^2) \cdot t^2 
\\  & + \left( (x_1-x_2)(v_{x_1}-v_{x_2})+(y_1-y_2)(v_{y_1}-v_{y_2}) \right )\cdot 2t 
\\  & +(x_1-x_2)^2+(y_1-y_2)^2

Wednesday, October 12, 2011

In-memory index structures

K-d tree (Point K-d tree)

Recursive subdivision of point-set into two halves using
vertical/horizontal line.
Horizontal line on even levels, vertical on odd levels
One point in each leaf
    Alternating splits on dimensions.
    Cost in two dimensions: O(√N + T) query time, O(N) storage
    Cost in higher dimensions: O(N^(1-1/d) + T) time complexity for d > 2
      Range tree
        Nested binary search trees
        Cost in two dimensions: O((logN)^2 + T) query time, O(NlogN) storage, Fractional cascading reduces query complexity to O(log N + T).
            Division into 4 subspaces
            Point and region versions
            Range query complexity similar to K-d tree

            Can be used for compressing/clustering
            information (Point versus region quadtree)


            Used for stabbing queries on 1-d intervals
            – Root defined by median end-point
            – Left child stores all intervals that end before the median
            – Right child stores all intervals that begin after the median
            – The root stores all intervals that intersect the median; order by left end-points and by right end-points in separate lists

            Used together with Range Tree for window query:
            O(N log N) storage, O(N log N) construction time, O((logN)^2 + T) query time

            Voronoi Diagram for NN Search

            O(N) space, O(N log N) construction time, O(logN) query time

            kth order Voronoi diagram defines the partitioning based on k-closest sites. For 2 dimensions, O(k(N-k)) space, O(k2N log k + kN log N) construction time, O(k + logN) query time.

            A number of approximate algorithms.


            Computational geometry, algorithms and applications, de Berg et al, Springer.