text:
\section{Introduction}

\subsection{Sorting in Two Dimensions}

Consider the following toy problem (in fact, a special case of offline
point location), which we call \emph{the slab problem}. We are given a
vertical slab in the plane, $m$ nonintersecting segments cutting
across the slab, and $n$ points in the slab. The goal is to identify
the segment immediately below each of the $n$ points. In other words,
we would like to sort the points ``relative to'' the segments.

This is an appealing and natural generalization to two dimensions of
the one-dimensional notion of sorting. It captures both an intuitive
notion of ordering, and the non-orthogonal flavor so common in
computational geometry.
Indeed,
as described below, an impressive collection of fundamental problems
in computational geometry are known to be reducible to this simple
problem, so there is a formal sense in which the slab problem is as
central in computational geometry as sorting is in the one-dimensional
world.

Classically, the slab problem is solved by binary searching among
segments for each input point, for a cost of $O(\lg m)$ per point.
This is optimal when one searches by binary decisions or assumes the
input has infinite precision, as on a real RAM. However, a more reasonable
assumption is that input has finite precision. We will assume, in
particular, that all coordinates come from some universe $[2^w]=\{ 0, \dots,
2^w-1 \}$, and that we are working on a word RAM with $w$-bit words
(i.e.~one coordinate fits in one word). See Section \nolinebreak\latexref{sec:why-ints}
for a discussion of these assumptions.

Until recently, successful use of the word RAM in computational
geometry was limited to a restricted class of problems, especially
problems involving orthogonal objects. However, in FOCS'06, we
proposed improved data structures for the
\emph{online} slab problem, a problem of a fundamentally nonorthogonal
nature~\nolinebreak\latexcite{ChaPat}.
The running time was asymptotically $\min \left\{ \frac{\lg
m}{\lg\lg m}, \sqrt{\frac{w}{\lg w}} \right\}$ per point. This
represents a marginal improvement over $O(\lg m)$ for \emph{any}
universe, and a roughly quadratic improvement for small (polynomial)
universes.

In the current paper, we describe an algorithm for the (offline) slab
problem running in time $n \cdot 2^{O(\sqrt{\lg\lg m})} + O(m)$. Note
that this bound does not depend on the universe (aside from assuming a
coordinate fits in a word), and is deterministic. The bound is a
dramatic improvement over our old bounds---note, for example, that
the new bound grows more slowly than $n \lg^\varepsilon m + m$ for any constant
$\varepsilon>0$. In addition, the new bound represents a much more convincing
improvement over the standard $O(n\lg m)$ bound, demonstrating the
power granted by bounded precision.

The relation between our current algorithm and our results from
\nolinebreak\latexcite{ChaPat} is best understood by a parallel to
integer sorting. There, the online problem (predecessor search) is
known to require comparatively large running times (e.g.~in terms
of $n$ alone, an $\Omega(\sqrt{\frac{\lg n}{\lg\lg n}})$ lower bound per
point is known~\nolinebreak\latexcite{BeaFic}).  Yet, one
can find
ways of manipulating information in the offline problem, such that the
bottleneck of using the online problem is avoided (e.g.~we can
sort in $O(n\sqrt{\lg\lg n})$ expected time~\nolinebreak\latexcite{HanThoFOCS02}). It should
be
understood that the purpose of this work is not to study ``bit
tricks'' in the word RAM model, but to study how information about
points and lines can be decomposed in algorithmically useful ways.

\subsection{Applications}

From \nolinebreak\latexcite{ChaPat} it follows that improved bounds
for the slab problem lead to improved upper bounds for many
fundamental problems in computational geometry
\nolinebreak\latexcite{BerBOOK,EdeBOOK,MulBOOK,OroBOOK,PreSha}. We list some here. As
before, the bounds do not depend on the universe for the coordinates.
All the reductions below, except the last, are randomized.

\begin{myenumerate}
\item We can compute the {\em convex hull\/} of $n$ points in three
  dimensions in expected time $n\cdot 2^{O(\sqrt{\lg\lg n})}$.  If the
  hull has $H$ vertices, the bound can be reduced to $n\cdot
  2^{O(\sqrt{\lg\lg H})}$.

\item We can compute the {\em Voronoi diagram\/} and the {\em Delaunay
   triangulation\/} of $n$ points in the plane in expected time
   $n\cdot 2^{O(\sqrt{\lg\lg n})}$.  As a consequence, we can also
   compute the {\em Euclidean minimum spanning tree\/} or solve the
   {\em largest empty circle\/} problem within the same time bound.

\item Given $n$ red points and $n$ blue points in the plane, we can
  compute the red point nearest to each blue point in expected time
  $n\cdot 2^{O(\sqrt{\lg\lg n})}$.

\item We can compute all $K$ intersections of $n$ line segments in the
  plane in expected time $n\cdot 2^{O(\sqrt{\lg\lg n})} + O(K)$. We
  can also construct the {\em trapezoidal decomposition\/} of the line
  segments within the same time bound.

\item We can triangulate a polygon with holes (or an environment with
  multiple disjoint polygons) with $n$ vertices total in
  time $n\cdot 2^{O(\sqrt{\lg\lg n})}$.
\end{myenumerate}

Problems like convex hulls and Voronoi diagrams date back to the dawn
of computational geometry, and for these problems standard $O(n\lg n)$
bounds have long been regarded as ``optimal.''  The previous paper
\nolinebreak\latexcite{ChaPat} has demonstrated that on the word RAM, $O(n\lg n)$
can be beaten slightly, by $O(n\frac{\lg n}{\lg\lg n})$ bounds.  The current
paper shows that $O(n\lg n)$ can be improved significantly.

\paragraph{Planar point location.}
The slab problem is actually a special case of the {\em offline planar
point location\/} problem.  Here, the input consists of a connected
polygonal subdivision defined by a set of $m$ segments in the plane,
where segments are only allowed to touch at endpoints. Given $n$ query
points (offline), the goal is to identify the polygon (face) which
contains each point.

In fact, reductions discussed above are to the offline planar point
location problem. However, the general case of point location turns
out to be reducible to the special case of the slab problem. In
\nolinebreak\latexcite{ChaPat}, we considered three different ways to
achieve this reduction. These three approaches hold both in the
offline and online cases. They all generate a multiplicative penalty
of at most $O(\lg\lg m)$ per point, which is absorbed by our time
bound, but differ in the cost per segment:
\begin{myenumerate}
\item[(i)] random sampling gives a \emph{randomized} $(n+m)\cdot
  2^{O(\sqrt{\lg\lg m})}$ running time.

\item[(ii)] persistence and exponential trees give a deterministic
  $n\cdot 2^{O(\sqrt{\lg\lg m})} + O(\textrm{sort}(m))$ bound, where
  $\textrm{sort}(m)$ denotes the cost of sorting $m$ integers.

\item[(iii)] planar separators are the most complicated (and least
  practical) strategy but give the best deterministic running time of
  $n \cdot 2^{O(\sqrt{\lg\lg m})} + O(m)$.
\end{myenumerate}

\paragraph{Higher dimensions.}
We can also solve the analog of the slab problem in any constant
dimension. Instead of a slab, we are given a vertical prism, and
instead of segments, we are given hyperplanes cutting across the prism
where no two hyperplanes intersect inside the prism. The running time of
our solution is $n\cdot 2^{O(\sqrt{\lg\lg m})} \lg^{1+o(1)} w + O(m)$.
Although the bound now has an extra $\lg^{1+o(1)}w$ factor, this
factor is relatively small.  This result has a few applications as
well, for example, to offline exact nearest neighbor search in higher
dimensions and curve-segment intersection in two dimensions (see
\nolinebreak\latexcite{ChaPat}).

\paragraph{Recent work.}
Subsequent to our conference publication, Buchin and
Mulzer~\nolinebreak\latexcite{BucMul} announced a better result for planar Voronoi
diagrams. They show that constructing Voronoi diagrams is equivalent
to sorting, in the Word RAM augmented with one non-standard
operation. In the standard Word RAM, they obtain an unconditional
running time of $O(n \sqrt{\lg\lg n})$ by adapting the best known
sorting algorithm of~\nolinebreak\latexcite{HanThoFOCS02}.

This improves the running time of all problems mentioned in item
2.~above. However, this algorithm exploits special properties about
Voronoi diagrams and nearest neighbor graphs, and does not imply
improved results for the other problems considered here, such as 3-d
convex hulls and offline point location.

\subsection{Computational Geometry on a Grid}  \label{sec:why-ints}

It is superfluous to state that bounded precision is a fact of
life. Input data are given with finite precision and computers
represent it internally in a bounded number of bits. Low-dimensional
computational geometry has typically seen the negative consequences of
this state of affairs. Algorithms are designed in idealized models of
real arithmetic, and practitioners struggle to keep the algorithms
working with imperfect precision.

Yet, there is also a good side to bounded precision, and our result
shows it can be used to achieve significantly better
algorithms. Again, we emphasize that our improved bound is independent
of whatever the bound on the precision happens to be. We just require
that coordinates can be manipulated in constant time, which has always
been a standard assumption.

The philosophical question that we wish to address briefly is whether
these benefits of bounded precision should be explored in theory. We
believe firmly they should, examining the question both with an eye to
practice and to theory.

\paragraph{Practice.}
From a theoretical perspective, the classic solutions to online point
location using linear space and logarithmic query time would seem
attractive. However, as pointed out in a survey on the topic
\nolinebreak\latexcite{SnoSURV}, the most efficient and popular practical
implementations do not use them. Instead, they use grid-pruning
heuristics, not unlike some of our ideas. Thus, we can hope to gain
theoretical understanding for what is already known to be effective in
the real world---a standard goal for theory.

Turning this around, we can hope that theoretical improvements will
suggest new ideas with an impact in practice. As presented, our
results are theoretical because of large hidden constants, in both the
slab problem and subsequent reductions. However, since the improvement
over $O(n\lg n)$ is now quite significant, we find it plausible that
some of the techniques developed here can provide inspiration for
useful practical ``tricks.'' A key step would be to circumvent the
reductions and apply our techniques directly to target problems.

\paragraph{Theory.}
Even at theory's end of computational geometry, the assumption of
bounded precision has been used fairly often. Unfortunately, this body
of work (see the bibliographies of \nolinebreak\latexcite{ChaPat})
has been plagued by close ties to one-dimensional
problems. For example, two-dimensional convex hulls can be found in
linear time once points are sorted by $x$-coordinate. More typically,
the problems considered involved orthogonal objects, and such
orthogonal problems can more easily be decomposed into one-dimensional
problems.

Our recent data structures for point location \nolinebreak\latexcite{ChaPat} broke this barrier, by presenting an improvement for a
fundamentally nonorthogonal problem. The current paper tries to
demonstrate that there are deeper questions to be explored in this
direction of research. In our algorithm, we are forced to consider
questions of decomposability and compressibility of information about
two-dimensional objects, which seem fundamentally different from
questions in one dimension. We feel this should have a theoretical
appeal in itself.

For example, consider two standard tools in sorting. One is radix
sort, which gives linear-time sorting in polynomial universes.
Another is hashing, which is used in virtually all advanced RAM
sorting algorithms, including
\nolinebreak\latexcite{AndFOCS96,AndJCSS,HanINFCOMP,HanSTOC02,HanThoFOCS02,KirRei,ThoSODA97}.
In two dimensions, neither of these tools seems
relevant.
It is interesting that even without such basic
tools, we can still obtain a rather efficient, determinstic algorithm
(even outperforming some of the older RAM sorting results).

\IGNORE{
\paragraph{What kind of bounded precision?}
The final question that we wish to touch on is whether an integer
universe is the right model for bounded precision. In certain cases,
the input is on an integer grid by definition (e.g.~objects are on a
computer screen). One might worry, however, about the input being a
floating point number. We believe that in most cases this is an
artifact of representation, and numbers should be treated as integers
after appropriate scaling. One reason is to note that the
``floating-point plane'' is simply a union of bounded integer grids
(the size depending on the number of bits of the mantissa), at
different scale factors around the origin. Since our problems are
translation-independent, there is no reason the origin should be
special, and having more detail around the origin is not particularly
meaningful. Another reason is that certain aspects of the problems are
not well-defined when inputs are floating point numbers. For example,
the slope of a line between two points of very different exponents is
not representable by floating point numbers anywhere close to the
original precision.
}

\subsection{Overview}

The remainder of this paper is organized as follows. In Section
\nolinebreak\latexref{sec:sqrt-lg}, we describe a simple algorithm for the slab
problem, running in time $O(n \sqrt{\lg m} + m)$. This demonstrates
the basic divide-and-conquer strategy behind our solution. In Section
\nolinebreak\latexref{sec:better}, we implement this strategy
much more carefully to obtain an interesting recurrence
that ultimately leads to the stated time bound of $n \cdot
2^{O(\sqrt{\lg\lg m})} +O(m)$. The challenges faced by this improvement are
similar to issues in integer sorting, and indeed we borrow (and build
upon) some tools from that field.

Unfortunately, the implementation of Section \nolinebreak\latexref{sec:better} requires
a nonstandard word operation. In Section \nolinebreak\latexref{sec:stdops}, we describe
how to implement the algorithm on a standard word RAM,
using only addition, multiplication, bitwise-logical
operations, and shifts.  Interestingly, the new implementation requires
some new geometric observations that affect the
design of the recursion
itself.

\section{An Initial Algorithm for the Slab Problem} \label{sec:sqrt-lg}

\subsection{The Basic Recursive Strategy}

We begin with a recursive strategy based on a simple observation,
taken from~\nolinebreak\latexcite{ChaPat}. (Later in Section \nolinebreak\latexref{sec:stdops}, we will
replace this with a more complicated recursive structure.)
In the following, the notation $\prec$ refers to the belowness
relation.

\newcommand{\tilde{s}}{\tilde{s}}

\begin{observation} \label{obs:basic}
Fix $b$ and $h$. Let $S$ be a set of $m$ sorted disjoint segments,
where all left endpoints lie on an interval $I_L$ of length
$2^{\ell_L}$ on a vertical line, and all right endpoints lie on an
interval $I_R$ of length $2^{\ell_R}$ on another vertical line.  In
$O(b)$ time, we can find $O(b)$ segments $s_0,s_1,\ldots\in S$ in
sorted order, which include the lowest segment of $S$, such that:
\begin{enumerate}
\item[\em (1)] for each $i$, at least one of the following holds:
  \begin{enumerate}
  \item[\em (1a)] there are at most $m/b$ segments of $S$ between $s_i$
    and $s_{i+1}$.
  \item[\em (1b)] the left endpoints of $s_i$ and $s_{i+1}$ lie on a
    subinterval of length $2^{\ell_L-h}$.
  \item[\em (1c)] the right endpoints of $s_i$ and $s_{i+1}$ lie on a
    subinterval of length $2^{\ell_R-h}$.
  \end{enumerate}

\item[\em (2)] there exist segments $\tilde{s}_0,\tilde{s}_2,\ldots$ cutting
  across the slab, satisfying all of the following:
  \begin{enumerate}
    \item[\em (2a)] $s_0 \prec \tilde{s}_0 \prec s_2 \prec \tilde{s}_2 \prec
      \cdots$.
    \item[\em (2b)] distances between the left endpoints of the
      $\tilde{s}_i$'s are all multiples of $2^{\ell_L-h}$.
    \item[\em (2c)] distances between right endpoints are all
      multiples of $2^{\ell_R-h}$.
  \end{enumerate}
\end{enumerate}
\end{observation}

\begin{figure}
\begin{center}
\setlength{\unitlength}{1.6in}
\input{slab.fig.tex}
\end{center}\vspace{-2.5ex}
\caption{Proof of Observation \protect\nolinebreak\latexref{obs:basic}: an example
(with $\ell_L=\ell_R$).
The left diagram shows the segments in $B$.}
\label{fig:slab}
\end{figure}

\newcommand{\mbox{\sc Slab}}{\mbox{\sc Slab}}
\newcommand{\mbox{\sc round}}{\mbox{\sc round}}
\newcommand{\mbox{\sc ans}}{\mbox{\sc ans}}
\newcommand{\mbox{\sc null}}{\mbox{\sc null}}

\begin{figure*}
\center
\fbox{\hspace{-.5cm}
\begin{minipage}{7cm}
  \begin{algm} $\mbox{\sc Slab}(Q,S)$:\\[2pt]
    0.\' if $m=0$, set all answers to $\mbox{\sc null}$ and return \\
    1.\' let $s_0, s_1, \ldots$ be the $O(b)$ segments from
      Observation \nolinebreak\latexref{obs:basic} \\
    2.\' let $\varphi$ be the projective transform mapping $I_L$ to
      $\{0\}\times [0,2^h]$ and $I_R$ to $\{2^h\}\times [0,2^h]$. \\
      \> Compute $\mbox{\sc round}(\varphi(Q))$ and
           $\varphi(\tilde{s}_0),\varphi(\tilde{s}_2),\ldots$ \\
    3.\' $\mbox{\sc Slab}_0(\mbox{\sc round}(\varphi(Q)),\:
      \{ \varphi(\tilde{s}_0),\varphi(\tilde{s}_2),\ldots \})$\\
    4.\' for each $q\in Q$ with
      $\mbox{\sc ans}[\mbox{\sc round}(\varphi(q))]=\varphi(\tilde{s}_i)$ do\\ \> set $\mbox{\sc ans}[q]=$
      the segment from $\{s_{i-4},\ldots, s_{i+7}\}$ immediately below
      $q$\\
    5.\' for each $s_i$ do\\
      \> $\mbox{\sc Slab}(\{q\in Q\mid \mbox{\sc ans}[q]=s_i\},\:
      \{s\in S\mid s_i\prec s\prec s_{i+1}\})$
  \end{algm}
\end{minipage}
\hspace{.5cm}}
\caption{A recursive algorithm for the slab problem. Parameters $b$
  and $h$ are fixed in the analysis; $\mbox{\sc round}(\cdot)$ maps a point to
  its nearest integral point.}
\label{fig:slab-code}
\end{figure*}

\begin{pf}
Let $B$ contain every $\down{m/b}$-th segment of $S$, starting with
the lowest segments $s_0$. Impose a grid over $I_L$ consisting of
$2^h$ subintervals of length $2^{\ell_L-h}$, and a grid over $I_R$
consisting of $2^h$ subintervals of length $2^{\ell_R-h}$. We define
$s_{i+1}$ inductively based on $s_i$, until the highest segment is
reached. We let $s_{i+1}$ be the highest segment of $B$ such that
either the left or the right endpoints of $s_i$ and $s_{i+1}$ are in
the same grid subinterval. This will satisfy (1b) or (1c). If no such
segment above $s_i$ exists, we simply let $s_{i+1}$ be the successor
of $s_i$, satisfying (1a).  (See Figure~\nolinebreak\latexref{fig:slab}.)

Let $\tilde{s}_i$ be obtained from $s_i$ by rounding each endpoint to the
grid point immediately above (ensuring (2b) and (2c)). By construction
of the $s_i$'s, both the left and right endpoints of $s_i$ and $s_{i+2}$
are in different grid subintervals. Thus, $\tilde{s}_i \prec s_{i+2}$,
ensuring (2a).
\end{pf}

\bigskip
The above observation naturally suggests a recursive algorithm.
In the pseudocode in
Figure \nolinebreak\latexref{fig:slab-code}, the input is a set $Q$
of $n$ points and a sorted set $S$ of $m$ disjoint segments, where the
left and right endpoints lie on intervals $I_L$ and $I_R$ of length
$2^{\ell_L}$ and $2^{\ell_R}$ respectively. At the end, $\mbox{\sc ans}[q]$
stores the segment from $S$ immediately below $q$ for each $q\in Q$.
A special $\mbox{\sc null}$ value for $\mbox{\sc ans}[q]$ signifies that $q$ is below all
segments. We assume a (less efficient) procedure $\mbox{\sc Slab}_0(Q,S)$, with
the same semantics as $\mbox{\sc Slab}(Q,S)$, which is used as a bottom case of
the recursion. The choice of $\mbox{\sc Slab}_0()$ is a crucial component of the
analysis.

\medskip

We first explain why the pseudocode works.  In step~2, an explicit
formula for the transform $\varphi$ has already been given
in~\nolinebreak\latexcite{ChaPat}; this mapping preserves the belowness relation.
According to property (2) in Observation \nolinebreak\latexref{obs:basic}, we know that
the transformed segments $\varphi(\tilde{s}_0), \varphi(\tilde{s}_2), \ldots$
all have $h$-bit integer coordinates from $[2^h]$. After rounding, the
$n$ points $\varphi(Q)$ will lie in the same universe.

Any unit square can intersect at most two of the $\varphi(\tilde{s}_i)$'s,
since these segments have vertical separation at least one and thus
horizontal separation at least one (as slopes are between $-1$ and
$1$).  If $\varphi(\tilde{s}_i) \prec \mbox{\sc round}(\varphi(q)) \prec
\varphi(\tilde{s}_{i+2})$, then we must have $\varphi(\tilde{s}_{i-4}) \prec
\varphi(q) \prec \varphi(\tilde{s}_{i+6})$, implying that $s_{i-4} \prec
\tilde{s}_{i-4} \prec q \prec \tilde{s}_{i+6} \prec s_{i+8}$.  Thus, at step~4,
$\mbox{\sc ans}[q]$ contains the segment from $s_0,s_1\ldots$ immediately below
$q$.  Once this is determined for every point $q\in Q$, we can
recursively solve the subproblem for the subset of points and segments
strictly between $s_i$ and $s_{i+1}$ for each $i$, as is done at
step~5.  An answer $\mbox{\sc ans}[q] = \mbox{\sc null}$ from the $i$-th subproblem is
interpreted as $\mbox{\sc ans}[q] = s_i$.

Let $\ell = (\ell_L + \ell_R)/2\ (\ell\le w)$. Denote by $T(n,m,\ell)$ the
running
time of $\mbox{\sc Slab}()$, and $T_0(n,b',h)$ the running time of the call to
$\mbox{\sc Slab}_0()$ in step~3.  Steps~1, 2 and~4 can be implemented naively in
$O(n+m)$ time.  We have the recurrence:
\begin{equation} \label{eq:basic-rec}
T(n,m,\ell)\ =\ T_0(n,b',h) \:+\: O(n+m) \:+\:
\sum_{i=0}^{b'} T(n_i,m_i,\ell_i),
\end{equation}
where $b'=O(b)$, $\sum_i n_i=n$, $\sum_i m_i = m-b'$. Furthermore,
according to property (1) in Observation~\nolinebreak\latexref{obs:basic}, for each $i$
we either have $m_i\le \frac{m}{b}$ or $\ell_i \le \ell-\frac{h}{2}$.
This implies that the depth of the recursion is $O(\log_b m +
\frac{\ell}{h})$.

\subsection{An $O(n\sqrt{\lg m} + m)$ Algorithm}

In the previous paper~\nolinebreak\latexcite{ChaPat}, we have noticed that for $b'
h\approx w$, $\mbox{\sc Slab}_0()$ can be implemented in $T_0(n,b',h)=O(n)$ time
by packing $b'$ segments from an $h$-bit universe into a word.
By setting $b\approx \log^\varepsilon m$ and $h\approx w/\log^\varepsilon m$,
this leads to an $O((n + m) \frac{\lg m}{\lg\lg m})$ algorithm.

Instead of packing multiple segments in a word, our new idea is to
pack {\em multiple points\/} in a word.  To understand why this helps,
remember that the canonical implementation for $\mbox{\sc Slab}_0()$ runs in
time $O(n\lg m)$ by choosing the middle segment and recursing on
points above and below this segment. By packing $t$ segments in a
word, we can hope to reduce this time to $O(n\log_t m)$. However, by
packing $t$ points in a word, we can potentially reduce this to
$O(\frac{n}{t} \lg m)$, a much bigger gain. (One can also think of
packing both points and segments, for a running time of $O(\frac{n}{t}
\log_t m)$. Since we will ultimately obtain a much faster algorithm,
we ignore this slight improvement.)

To implement this idea, step 2 will pack $\mbox{\sc round}(\varphi(Q))$ with $O(w
/ h)$ points per word. Each point is alotted $O(h)$ bits for the
coordinates, plus $\lg b = O(h)$ bits for the answer
$\mbox{\sc ans}[\mbox{\sc round}(\varphi(q))]$ which $\mbox{\sc Slab}_0()$ must output. This packing
can be done in $O(n)$ time, adding one point at a time.

Working on packed points, $\mbox{\sc Slab}_0()$ has the potential of running
faster, as evidenced by the following lemma. For now, we do not
concern ourselves with the implementation on a word RAM, and assume
nonstandard operations (an operation takes two words as input, and
outputs one word).

\begin{lemma}   \label{lem:basic-zero}
If $\lg b \le h\le w$,
$\mbox{\sc Slab}_0()$ can be impemented on a RAM with nonstandard operations
with a running time of $T_0(n,b,h) = O(n \frac{h}{w} \lg
b + b)$.
\end{lemma}

\begin{pf}
Given a segment and a number of points packed in a word, we can
postulate two operations which output the points above (respectively
below) the segment, packed consecutively in a word. Choosing a
segment, we can partition the points into points above and below the
segment in $O(\lceil n \frac{h}{w} \rceil)$ time. In the same
asymptotic time, we can make both output sets be packed with $\lfloor
\frac{w}{h} \rfloor$ points per word (merging consecutive words which
are less than full).

We now implement the canonical algorithm: partition points according
to the middle segment and recurse. As long as we are working with $\ge
\frac{w}{h}$ points, the cost is $O(\frac{h}{w})$ per point for each
segment, and each point is considered $O(\lg b)$ times. If we are
dealing with less than $\frac{w}{h}$ points, the cost is $O(1)$, and
that can be charged to the segment considered. Thus, the total time
after packing is $O(n\frac{h}{w}\lg b + b)$.

The last important issue is the representation of the output. By the
above, we obtain the sets of points which lie between two consecutive
segments. We can then trivially fill in the answer for every point in
the $\lg b$ bits alotted for that.  However, we want an array of
answers for the points in the original order. To do that, we trace the
algorithm from above backwards in time. We use an operation which is
the inverse of splitting a word into points above and below a segment.
\end{pf}

\bigskip

Plugging the lemma into (\nolinebreak\latexref{eq:basic-rec}), we get $T(n, m,\ell) =
O( n \frac{h}{w}\lg b + n + m ) \cdot O(\log_b m +
\frac{\ell}{h})$.  Setting $\lg b = \sqrt{\lg m}$ and $h= w /
\sqrt{\lg m}$, we obtain $T(n,m,w)=O((n+m) \sqrt{\lg m})$.  This can
be improved to $O(m + n\sqrt{\lg m})$ by the standard trick of
considering only one in $O(\sqrt{\lg m})$ consecutive segments. For
every point, we finish off by binary searching among $O(\sqrt{\lg m})$
segments, for a negligible additional time of $O(n\lg\lg m)$.

\section{An $n \cdot 2^{O(\sqrt{\lg\lg m})} + O(m)$ Algorithm}
\label{sec:better}

\subsection{Preliminaries}

To improve on the $O(m+n\sqrt{\lg m})$ bound, we {\em bootstrap\/}: we use
an improved algorithm for $\mbox{\sc Slab}()$ as $\mbox{\sc Slab}_0()$, obtaining an even
better bound for $\mbox{\sc Slab}()$. To enable such improvements, we can no
longer afford the $O(n)$ term in the recurrence (\nolinebreak\latexref{eq:basic-rec}).
Rather, a call to $\mbox{\sc Slab}()$ is passed $Q$ in word-packed form, and we
want to implement the steps between recursive calls in {\em
sub\/}linear time (close to the number of words needed to represent
$Q$, not to $n=|Q|$).

This task will require further ideas and more sophisticated
word-packing tricks. To understand the complication, let us contrast
implementing steps~2 and~5 of $\mbox{\sc Slab}()$ in sublinear time. Computing
$\mbox{\sc round}(\varphi(Q))$ in Step 2 is solved by applying a function in
parallel to a word-packed vector of points. This is certainly
possible, at least using nonstandard word operations. However, step 5
needs to group elements of $Q$ into subsets (i.e.~sort $Q$ according
to $\mbox{\sc ans}[q]$). This is a deeper information-theoretic limitation, and
it is rather unlikely that it can always be done in time linear in the
number of words needed to store $Q$. The problem has connections to
applying permutations in external memory, a well-studied problem which
is believed to obey similar limitations \nolinebreak\latexcite{AggVit}.

\newcommand{\mbox{\sc Split}}{\mbox{\sc Split}}
\newcommand{\mbox{\sc Unsplit}}{\mbox{\sc Unsplit}}
\newcommand{\mbox{\sc label}}{\mbox{\sc label}}

\medskip

To implement step 5 (and also step 4), we will use a subroutine
$\mbox{\sc Split}(Q, \mbox{\sc label})$. This receives a set $Q$ of $\ell$-bit elements,
packed in $O(n\frac{\ell}{w})$ words. Each elements $q\in Q$ has a
$(\lg m)$-bit label $\mbox{\sc label}[q]$ with $\lg m\le\ell$.  The labels are stored
in the same $O(n\frac{\ell}{w})$ words.  We can think of each word
as consisting of two portions, the first containing $O(\frac{w}{\ell})$
elements and the second containing the corresponding
$O(\frac{w}{\ell})$ labels.
The output of $\mbox{\sc Split}(Q, \mbox{\sc label})$ is a collection
of sublists, so that all elements of $Q$ with the same label are put
in the same sublist (in arbitrary order).

In addition, we will need $\mbox{\sc Split}()$ to be reversible. Suppose the
labels in the sublists have been modified. We need a subroutine
$\mbox{\sc Unsplit}(Q)$, which outputs $Q$ in the original order before
$\mbox{\sc Split}()$, but with the modified labels attached.

The following lemma states the time bound we will use for these two
operations. The implementation of $\mbox{\sc Split}()$ is taken from a paper by
Han~\nolinebreak\latexcite{HanINFCOMP} and has been also used as a subroutine in
several integer sorting algorithms \nolinebreak\latexcite{HanSTOC02,HanThoFOCS02}.  As
far as we know, the observation that $\mbox{\sc Unsplit}()$ is possible in the
same time bound has not been stated explicitly before.

\begin{lemma} \label{lem:split}
Assume $\mbox{\sc label}[q] \in [m]$ for all $q\in Q$, and let $M$ be a
parameter. If $\frac{w}{\ell}\lg m \le \frac{1}{2} \lg M$ and $\lg m
\le \ell \le w$, both $\mbox{\sc Split}()$ and $\mbox{\sc Unsplit}()$ require time
$O(n\frac{\ell}{w}\lg \frac{w}{\ell} + M)$.
\end{lemma}

\begin{pf}
Let $g = \frac{w}{\ell}$. Each word contains $g$ elements, with $g\lg
m$ bits of labels. Put words with the same label pattern in the same
bucket. This can be done in $O(n/g + \sqrt{M})$ time, since the number
of different label patterns is at most $2^{g\lg m}\le \sqrt{M}$.  For
each bucket, we form groups of $g$ words and {\em transpose\/} each
group to get $g$ new words, where the $i$-th element of the $j$-th new
word is the $j$-th element of the $i$-th old word.  Transposition can
be implemented in $O(\lg g)$ standard word operations~\nolinebreak\latexcite{ThoSODA97}.
Elements in each new word now have identical labels.  We can put these
words in the correct sublists, in $O(n/g + m)$ time.  There are at
most $g$ leftover elements per bucket, for a total of
$O(\sqrt{M}g)=o(M)$; we can put them in the correct sublists in $o(M)$
time.  The total time is therefore $O((n/g)\lg g + M)$.

To support unsplitting, we remember information about the splitting
process.  Namely, whenever we transpose $g$ words, we create a record
pointing to the $g$ old words and the $g$ new words.  To unsplit, we
examine each record created
and transpose its $g$ new words again to get back
the $g$ old words (with labels now modified).  We can also update
the leftover elements by creating $o(M)$ additional pointers.
\end{pf}

\bigskip

A particularly easy application of this machinery is to implement the
algorithm of Section \nolinebreak\latexref{sec:sqrt-lg} with standard operations (with
a minor $\lg\lg m$ slowdown). This result is not interesting by
itself, but it will be used later as the base case of our
bootstrapping strategy.

\begin{corollary}  \label{cor:zero}
If $\frac{w}{h}\lg b \le \frac{1}{2} \lg M$ and $\lg b\le h\le w$,
the algorithm for $\mbox{\sc Slab}_0()$ from Lemma \nolinebreak\latexref{lem:basic-zero} can be
implemented on a word RAM with standard operations in time
$T_0(n,b,h)=O(n \frac{h}{w} \lg b\,\lg \frac{w}{h} + bM)$.
\end{corollary}

\begin{pf}
The nonstandard operations used before were splitting and unsplitting
a set of points packed in a word, depending on sidedness with respect
to a segment. It is not hard to compute sidedness of all points from a
word in parallel using standard operations: we apply the linear map
defining the support of the segment to all points (which is a parallel
multiplication and addition), and keep the sign bits of each
result. The sign bits define 1-bit labels for the points, and we can
apply $\mbox{\sc Split}()$ and $\mbox{\sc Unsplit}()$ for these.
\end{pf}

\bigskip

Since the algorithm is used with $b=\sqrt{\lg m}$ and $h= w/\sqrt{\lg m}$,
we
incur a slowdown of $O(\lg\frac{w}{h})=O(\lg\lg m)$ per point compared to
the implementation
with nonstandard operations. By setting $M=m^2$,
the algorithm of the previous section would then
run in time $O(n\sqrt{\lg m} \lg\lg m + m^3)$ if implemented with
standard operations.  (The dependence of the second term on $m$ can be
lowered as well.)

\subsection{The Improved Algorithm}

\newcommand{{\widetilde{\ell}}}{{\widetilde{\ell}}}
\newcommand{\widetilde{m}}{\widetilde{m}}

Our fastest algorithm follows the same pseudocode of Figure
\nolinebreak\latexref{fig:slab-code}, but with a more careful implementation of the
individual steps. Let ${\widetilde{\ell}}$ be the number of bits per point and
$\widetilde{m}$ the original number of segments in the root call to $\mbox{\sc Slab}()$.
We have $\lg\widetilde{m}\le{\widetilde{\ell}}\le w$. In a recursive call to $\mbox{\sc Slab}()$, the
input consists of some $n$ points and $m\le\widetilde{m}$ segments, all with
coordinates from $[2^\ell]$, where $\ell\le {\widetilde{\ell}}$. Points will be
packed in $O({\widetilde{\ell}})$ bits each, so the entire set $Q$ occupies
$O(n\frac{{\widetilde{\ell}}}{w})$ words. At the end, the output $\mbox{\sc ans}[q]$ is
encoded as a label with $\lg\widetilde{m}$ bits, stored within each point $q\in
Q$, with the order of the points unchanged in the list~$Q$. Note that
one could think of repacking more points per word as $\ell$ and
$m$ decrease, but this will not yield an asymptotic advantage, so
we avoid the complication (on the other hand, repacking before the
call to $\mbox{\sc Slab}_0()$ is essential).

In step~2, we can compute $\mbox{\sc round}(\varphi(Q))$ in time linear in the
number of words $O(n\frac{{\widetilde{\ell}}}{w})$, by using a nonstandard word
operation that applies the projective transform (and rounding) to
multiple points packed in a word. Unfortunately, it does not appear
possible to implement this efficiently using standard operations. We
will deal with this issue in Section \nolinebreak\latexref{sec:stdops}, by changing the
algorithm for $\mbox{\sc Slab}()$ so that we only require affine
transformations, not projective transformations.

Before the call to $\mbox{\sc Slab}_0()$ in step~3, we need to condense the
packing of the points $\mbox{\sc round}(\varphi(Q))$ to take up $O(n\frac{h}{w})$
words. Previously, we had $O(\frac{w}{{\widetilde{\ell}}})$ points per word, but
after step~2, only $O(h)$ bits of each point were nonzero.  We will
stipulate that points always occupy an number of bits which is a power
of 2.  This does not affect the asymptotic running time.  Given this
property, we obtain a word of $\mbox{\sc round}(\varphi(Q))$ by condensing ${\widetilde{\ell}}
/ h$ words.  This operation requires shifting each old word, and {\sc
or}ing it into the new word.

Note that the order of $\mbox{\sc round}(\varphi(Q))$ is different from the order
of $Q$, but this is irrelevant, because we can also reverse the
condensing easily. We simply mask the bits corresponding to old word,
and shift them back. Thus, we obtain the labels generated by
$\mbox{\sc Slab}_0()$ in the original order of $Q$. Both condensing and its
inverse take $O(n \frac{{\widetilde{\ell}}}{w})$ time.

For the remainder of the steps, we need to $\mbox{\sc Split}()$ and $\mbox{\sc Unsplit}()$.
For that, we fix a parameter $M$ satisfying $\frac{w}{{\widetilde{\ell}}} \lg \widetilde{m}
\le \frac{1}{2} \lg M$. In step~4, we first split the list
$\mbox{\sc round}(\varphi(Q))$ into sublists with the same $\mbox{\sc ans}$ labels. For each
sublist, we can perform the constant number of comparisons per point
required in step~4, and then record the new $\mbox{\sc ans}$ labels in the list,
in time linear in the number of words $O(n\frac{{\widetilde{\ell}}}{w})$. It is
standard to implement this in the word RAM by parallel multiplications
(see the proof of Lemma \nolinebreak\latexref{lem:split}). To complete step 4, we
$\mbox{\sc Unsplit}()$ to get back the entire list $\mbox{\sc round}(\varphi(Q))$, and then
copy the $\mbox{\sc ans}$ labels to the original list $Q$ in
$O(n\frac{{\widetilde{\ell}}}{w})$ time. Since both lists are in the same order,
this can be done by masking labels and {\sc or}ing them in.

To perform step~5, we again split $Q$ into sublists with the same
$\mbox{\sc ans}$ labels.  After the recursive calls, we unsplit to get $Q$ back
in the original order, with the new $\mbox{\sc ans}$ labels.

\subsection{Analysis}

For $\frac{w}{{\widetilde{\ell}}}\lg\widetilde{m}\le\frac{1}{2}\lg M$ and
$\lg\widetilde{m}\le{\widetilde{\ell}}\le w$,
the recurrence (\nolinebreak\latexref{eq:basic-rec}) now becomes:

\begin{equation}  \label{eq:new-rec}
T(n,m,\ell)\ =\ T_0(n,b',h)
\:+\: O\left(n\frac{{\widetilde{\ell}}}{w}\lg\frac{w}{{\widetilde{\ell}}} + M\right)
\:+\: \sum_{i=0}^{b'} T(n_i,m_i,\ell_i),
\end{equation}
where $b'=O(b)$, $\sum_i n_i=n$, $\sum_i m_i = m-b'$, and for each
$i$, we either have $m_i\le \frac{m}{b}$ or $\ell_i \le \ell -
\frac{h}{2}$. As before, the depth of the recursion is bounded by
$O(\log_b \widetilde{m} + \frac{{\widetilde{\ell}}}{h})$.

Assume that for $\frac{w}{h} \lg b \le \frac{1}{2}\lg M$ and $\lg b
\le h \le w$, an algorithm with running time
\[ T_0(n,b,h)\ \le\ c_k
   \left(n\frac{h}{w} \lg^{1/k} b\:\lg\left(\frac{w}{h}\lg b\right)
   \:+\: bM\right)
\]
is available to begin with. This is true for $k=1$ with $c_1=O(1)$
by Corollary \nolinebreak\latexref{cor:zero}.

Then the recurrence (\nolinebreak\latexref{eq:new-rec}) yields:

\[ T(n,\widetilde{m},{\widetilde{\ell}})\ =\ O(c_k) \cdot \left(
   \left[ n\frac{h}{w} \lg^{1/k} b\:\lg\left(\frac{w}{h} \lg b\right)
          \:+\: n \frac{{\widetilde{\ell}}}{w} \lg \frac{w}{{\widetilde{\ell}}} \right]
   \cdot \left( \log_b \widetilde{m} + \frac{{\widetilde{\ell}}}{h} \right) \:+\: mM\right).
\]

Set $\lg b = \lg^{k/(k+1)} \widetilde{m}$ and $h = {\widetilde{\ell}} \mbox{\big /}
\lg^{1/(k+1)} \widetilde{m}$.  Notice that indeed $\frac{w}{h} \lg b =
\frac{w}{{\widetilde{\ell}}} \lg\widetilde{m} \le \frac{1}{2} \lg M$ and $\lg b \le h \le w$.
Thus, we obtain an algorithm with running time:
\[ T(n,\widetilde{m},{\widetilde{\ell}})\ \le\ c_{k+1} \left(
   n \frac{{\widetilde{\ell}}}{w}\log^{1/(k+1)} \widetilde{m}\:\lg\left( \frac{w}{{\widetilde{\ell}}} \lg\widetilde{m} \right)
   \:+\: \widetilde{m} M\right)
\]
for some $c_{k+1}=O(1) \cdot c_k$.

Iterating this process $k$ times, we get:
\[ T(n,\widetilde{m},{\widetilde{\ell}})\ \le\ 2^{O(k)} \left(
   n \frac{{\widetilde{\ell}}}{w}\lg^{1/k}\widetilde{m}\:\lg\left( \frac{w}{{\widetilde{\ell}}} \lg\widetilde{m} \right)
   \:+\: \widetilde{m} M\right)
\]
for any value of $k$. Choosing $k=\sqrt{\lg\lg \widetilde{m}}$ to asymptotically
minimize the expression, and plugging in ${\widetilde{\ell}}=w$ and $M=\widetilde{m}^2$ (so
that indeed $\frac{w}{{\widetilde{\ell}}} \lg\widetilde{m} \le \frac{1}{2}\lg M$), we get:
\[ T(n,\widetilde{m},w)\ =\ 2^{O(\sqrt{\lg\lg\widetilde{m}})} \: (n  \:+\: \widetilde{m}^3).
\]

We can reduce the dependence on $\widetilde{m}$ to linear as follows. First,
select one out of every $\widetilde{m}^{3/4}$ consecutive segments of $S$, and
run the above algorithm on just these $\widetilde{m}^{1/4}$ segments. This takes
time $2^{O(\sqrt{\lg\lg\widetilde{m}})} (n+\widetilde{m}^{3/4})$ time. Now recurse
between each consecutive pair of selected segments.  The depth of the
recursion is $O(\lg\lg\widetilde{m})$, and it is straightforward to verify
that the running time is $n \cdot 2^{O(\sqrt{\lg\lg\widetilde{m}})} + O(\widetilde{m})$.

\section{Avoiding Nonstandard Operations}  \label{sec:stdops}

The only nonstandard operation used by the algorithm of Section
\nolinebreak\latexref{sec:better} is applying a projective transform in parallel to
points packed in a word. Unfortunately, it does not seem possible to
implement this in constant time using standard word RAM operations
(since, according to the formula for projective transform,
this operation requires multiple divisions where the divisors are all
different).

One idea is to simulate the special operation in slightly
superconstant time. We can use the circuit simulation results of
Brodnik et al.~\nolinebreak\latexcite{Bro} to reduce the operation to $\lg w \cdot
(\lg\lg w)^{O(1)}$ standard operations.
For the version of the slab problem in dimension 3 or higher,
this is the best approach we know.  Note that the results from the previous
section hold in any constant dimension, by simply using the
multidimensional analog of Observation \nolinebreak\latexref{obs:basic} from
\nolinebreak\latexcite{ChaPat}.

However, in two dimensions we can get rid of the dependence on the
universe, obtaining a time bound of $n\cdot 2^{O(\sqrt{\lg\lg m})}+O(m)$ on
the standard word RAM\@. This constitutes the object of this section.

\subsection{The Center Slab}

By horizontal translation, we can assume the left boundary of our
vertical slab is the $y$-axis. Let the abscissa of the right boundary
be $\Delta$. For some $h$ to be determined, let the \emph{center slab}
be the region of the plane defined by $\Delta / 2^h \le x \le \Delta
\cdot (1 - 2^{-h})$. The lateral slabs are defined in the intuitive
way: the left slab by $0 \le x \le \Delta / 2^h$ and the right slab by
$\Delta \cdot (1 - 2^{-h}) \le x \le \Delta$.

The key observation is that distances are somewhat well-behaved in the
center slab, so we will be able to decrease both the left and right
intervals at the same time, not just one of them. This enables us to
use (easier to implement) affine maps instead of projective
maps. Center slabs were also used in one of our previous papers
\nolinebreak\latexcite{PatFOCS06}, but as presented there, the idea cannot get rid of
the dependence on the universe. This paper's definition and use of the
center slab is rather different, and gets rid of this dependence.

The following is a replacement for Observation \nolinebreak\latexref{obs:basic}:

\begin{observation}  \label{obs:center}
Fix $b$ and $h$. Let $S$ be a set of $m$ sorted disjoint segments,
such that all left endpoints lie on an interval $I_L$ and all right
endpoints lie on an interval $I_R$, where both $I_L$ and $I_R$ have
length $2^\ell$. In $O(b)$ time, we can find $O(b)$ segments $s_0,
s_1, \ldots \in S$ in sorted order, which include the lowest segment
of $S$, such that:
\begin{enumerate}
\item[\em (1)] for each $i$, at least one of the following holds:
  \begin{enumerate}
  \item[\em (1a)] there are at most $m/b$ segments of $S$ between
    $s_i$ and $s_{i+1}$.
  \item[\em (1b)] both the left and right endpoints of $s_i$ and
    $s_{i+1}$ are at distance at most $2^{\ell-h}$.
  \end{enumerate}

\item[\em (2)] there exist segments $\tilde{s}_0 \prec \tilde{s}_1 \prec \cdots$
  cutting across the slab, satisfying all of the following:
  \begin{enumerate}
  \item[\em (2a)] distances between the left endpoints of the
    $\tilde{s}_i$'s are multiples of $2^{\ell-2h}$.
  \item[\em (2b)] ditto for the right endpoints.
  \item[\em (2c)] inside the center slab, $s_0 \prec \tilde{s}_0 \prec s_2
    \prec \tilde{s}_2 \prec \cdots$.
  \end{enumerate}
\end{enumerate}
\end{observation}

\begin{pf}
Let $B$ contain every $\down{m/b}$-th segment of $S$, starting with
the lowest segment $s_0$. We define $s_{i+1}$ inductively. If the next
segment after $s_i$ has either the left or right endpoints at distance
greater than $2^{\ell-h}$, let $s_{i+1}$ be this segment, which
satisfies (1a). Otherwise, let $s_{i+1}$ be the \emph{highest} segment
of $B$ which satisfies (1b).

Now impose grids over $I_L$ and $I_R$, both consisting of $2^{2h}$
subintervals of length $2^{\ell-2h}$.  We obtain $\tilde{s}_i$ from $s_i$
by rounding each endpoint to the grid point immediately above.  This
immediately implies $\tilde{s}_0 \prec \tilde{s}_1 \prec \cdots$ and $s_i \prec
\tilde{s}_i$.  Unfortunately, $\tilde{s}_i$ and $s_{i+k}$ may intersect for
arbitrarily large $k$ (e.g.~$s_i ,\ldots, s_{i+k}$ are very close on the
left, while each consecutive pair is far on the right). However, we
will show that inside the center slab, $\tilde{s}_i \prec s_{i+2}$.
(See Figure~\nolinebreak\latexref{fig:center}.)

By construction, $s_i$ and $s_{i+2}$ are vertically separated by more
than $2^{\ell-h}$ either on the left or on the right. Since lateral
slabs have a fraction of $2^{-h}$ of the width of the entire slab, the
vertical separation exceeds $2^{\ell-h} / 2^h = 2^{\ell - 2h}$
anywhere in the center slab. Rounding $s_i$ to $\tilde{s}_i$ represents a
vertical shift of less than $2^{\ell-2h}$ anywhere in the slab. Hence,
$\tilde{s}_i \prec s_{i+2}$ in the center slab.
\end{pf}

\bigskip

\begin{figure}
\begin{center}
\setlength{\unitlength}{1.6in}
\input{center.fig.tex}
\end{center}\vspace{-2.5ex}
\caption{Proof of Observation \protect\nolinebreak\latexref{obs:center}: a center slab.}
\label{fig:center}
\end{figure}

We now describe how to implement $\mbox{\sc Slab}()$, assuming the intervals
containing the left endpoints ($I_L$) and the right endpoints ($I_R$)
both have length $2^{\ell}$. In this section, we only deal with points
in the center slab. It is easy to $\mbox{\sc Split}()$ $Q$ into subsets
corresponding to the center and lateral slabs, and $\mbox{\sc Unsplit}()$ at the
end.

We use Observation \nolinebreak\latexref{obs:center} instead of Observation
\nolinebreak\latexref{obs:basic}. Since $I_L$ and $I_R$ have equal length, the map
$\varphi$ is affine. Thus, it can be implemented using parallel
multiplication and parallel addition. This means step~2 can be
implemented in time $O(n \frac{{\widetilde{\ell}}}{w})$ using standard operations.

Because we only deal with points in the center slab, and there $s_i
\prec \tilde{s}_i \prec s_{i+2}$ (just like in the old Observation
\nolinebreak\latexref{obs:basic}), steps 4 and 5 work in the same way.

\subsection{Lateral Slabs}

To deal with the left and right slabs, we use the following simple
observation, which we only state for the left slab by symmetry. Note
that the guarantees of this observation (for the left slab) are
virtually identical to that of Observation \nolinebreak\latexref{obs:center} (for the
center slab). Thus, we can simply apply the algorithm of the previous
section for the left and right slabs.

\newcommand{\tilde{t}}{\tilde{t}}

\begin{observation}  \label{obs:left}
Fix $b$ and $h$. Let $S$ be a set of $m$ sorted disjoint segments,
such that all left endpoints lie on an interval $I_L$ and all right
endpoints lie on an interval $I_R$, where both $I_L$ and $I_R$ have
length $2^\ell$. In $O(b)$ time, we can find $O(b)$ segments $t_0,
t_1, \ldots \in S$ in sorted order, which include the lowest segment
of $S$, such that:
\begin{enumerate}
\item[\em (1)] for each $i$, at least one of the following holds:
  \begin{enumerate}
  \item[\em (1a)] there are at most $m/b$ segments of $S$ between
    $s_i$ and $s_{i+1}$.
  \item[\em (1b)] anywhere in the left slab, the vertical separation
    between $s_i$ and $s_{i+1}$ is less than $2^{\ell-h+1}$.
  \end{enumerate}

\item[\em (2)] there exist segments $\tilde{t}_0 \prec \tilde{t}_1 \prec \cdots$
  cutting across the left slab, satisfying all of the following:
  \begin{enumerate}
  \item[\em (2a)] distances between the left endpoints of the
    $\tilde{t}_i$'s are multiples of $2^{\ell-2h}$.
  \item[\em (2b)] ditto for the right endpoints.
  \item[\em (2c)] inside the left slab, $t_0 \prec \tilde{t}_0 \prec t_2 \prec
    \tilde{t}_2 \prec \cdots$.
  \end{enumerate}
\end{enumerate}
\end{observation}

\begin{pf}
Let $I_A$ be the vertical interval at the intersection of the right
edge of the left slab with the parallelogram defined by $I_L$ and
$I_R$. Note $I_A$ also has size $2^\ell$.

Let $B$ contain every $\down{m/b}$-th segment of $S$, starting with
the lowest segment $t_0$. Given $t_i$, we define $t_{i+1}$ to be the
highest segment of $B$ which has the left endpoint at distance at most
$2^{\ell-h}$ away. If no such segment above $t_i$ exists, let
$t_{i+1}$ be the successor of $t_i$ in $B$ (this will satisfy
(1a)). In the first case, (1b) is satisfied because the right
endpoints of $t_i$ and $t_{i+1}$ are at distance most $2^\ell$, so on
$I_A$, the separation is at most $2^{\ell-h} (1 - 2^{-h}) + 2^{\ell}
\cdot 2^{-h} < 2^{\ell-h+1}$.

Now impose grids over $I_L$ and $I_A$, both consisting of $2^{h+1}$
subintervals of length $2^{\ell-h-1}$. We obtain $\tilde{t}_i$ from $t_i$ by
rounding the points on $I_L$ and $I_A$ to the grid point immediately
above. Note that the vertical distance between $t_i$ and $\tilde{t}_i$ is
less than $2^{\ell-h-1}$ anywhere in the left slab. On the other hand,
the left endpoints of $t_i$ and $t_{i+2}$ are at distance more than
$2^{\ell-h}$. The distance on $I_A$ (and anywhere in the left slab) is
at least $2^{\ell-h} (1-2^{-h}) \ge 2^{\ell-h-1}$. Thus $t_i \prec
\tilde{t}_i \prec t_{i+2}$.  (See Figure~\nolinebreak\latexref{fig:lateral}.)
\end{pf}

\begin{figure}
\begin{center}
\setlength{\unitlength}{1.6in}
\input{lateral.fig.tex}
\end{center}\vspace{-2.5ex}
\caption{Proof of Observation \protect\nolinebreak\latexref{obs:left}: a left slab.}
\label{fig:lateral}
\end{figure}

\subsection{Bounding the Dependence on $m$}

Our analysis needs to be modified,
because segments are simultaneously in the left, center and
right slabs, so they are included in 3 recursive calls.  In other
words, in recurrence (\nolinebreak\latexref{eq:new-rec}), we have to replace
$\sum_i m = m -b'$ with a weaker inequality $\sum_i m \le 3m$.
Recall that for our choice of $b$ and $h$, the depth of the
recursion is bounded by $O(\log_b \widetilde{m} + \frac{{\widetilde{\ell}}}{h})=
O(\lg^{1/(k+1)}\widetilde{m})$.
Thus, the cost per segment is increased by an
extra factor of $3^{O(\lg^{(1/(k+1)}\widetilde{m})}=3^{O(\sqrt{\lg\widetilde{m}})}$
for each bootstrapping round; the cost per point does not change.
With $k=\sqrt{\lg\lg\widetilde{m}}$ rounds, the overall dependence on $\widetilde{m}$
is now increased slightly to
$2^{O(\sqrt{\lg\lg\widetilde{m}})}\cdot \widetilde{m}^3\cdot 3^{O(\sqrt{\lg\widetilde{m}}\lg\lg\widetilde{m})})=
O(\widetilde{m}^{3+\varepsilon})$.
As before, this can be made $O(\widetilde{m})$ by working with
$\widetilde{m}^{1/4}$ segments and recursing.

\section{Open Problems}

Though our algorithm for offline point location is deterministic, the
reductions to other problems \nolinebreak\latexcite{ChaPat}
introduce randomization. It would be nice
to derandomize them. Another interesting question is
whether some of
these reductions also hold in the other direction.  For example,
the trapezoidal decomposition problem of disjoint line
segments is clearly no easier than offline point location, but
can the same be said for other problems like 3-d convex hulls?

A problem with an $O(n\lg n)$ upper bound that we currently cannot
improve is \emph{counting} intersections between a set of red segments
and a set of blue segments, given that no segments of the same color
intersect~\nolinebreak\latexcite{ChEdGuALGMCA}.  Note that this problem is no easier
than counting inversions in a permutation, which takes $O(n \sqrt{\lg
  n})$ time by the best known algorithm~\nolinebreak\latexcite{cp10invs}.

Finally, the complexity of the online point location problem
remains open: can the
$O(\frac{\lg n}{\lg\lg n})$ and $O(\sqrt{\frac{w}{\lg w}})$ upper
bounds from \nolinebreak\latexcite{ChaPat} be improved, or can
stronger lower bounds be proved?

\small
\renewcommand{\baselinestretch}{0.98}

\bibliographystyle{abbrv}


text:
GTA VI Could be on the Horizon
By Jeff Williams
Feb 6, 2015 02:22 EST
Grand Theft Auto has been one of the more successful gaming franchises as of late, with Rockstar announcing that hey have sold more that 45 Million copies of the very well reviewed and incredibly fun Grand Theft Auto 5 on Xbox and PS4 after having only been out since November of 2014. This is a number which handily beats the total amount of copies of GTA IV that were sold from 2008 until 2013, which was around 25 Million.
Fan speculation as to what GTA VI could entail.
Grand Theft Auto VI - enough said
But what does this say of the future of the franchise? Now that GTA V is released for all major players, except for the PC, where does this particular franchise go today? Leslie Benzies, the president of Rockstar North had apparently told Develop Magazine back in 2013 that they have quite a lot of content planned as DLC for GTAV, Online and perhaps even a future standalone game.
"We've got about 45 years worth of ideas we want to do," Benzies laughs. "We don't know what GTA VI will be, but we've got some ideas. GTA Online is the focus right now. There ain't no rest between finishing V and then Online. Plus we have some other things – stuff, DLC, I don't know how to describe it exactly – that we'd like to do, and we'll pick the right ones."
This is all excellent news that they are committed to the growth of a very viable brand, but which direction is going to be their next? LA and the various fun-filled avenues of adventure were the focus for quite some time, but what ideas could they possibly pull out of their hats for the next go around? I feel that this genre is a good one, the openness of the world brings with it great possibilities, but at the same time it could be a very easy trap to fall into to rehash old ideas and get into a cycle of boredom. GTA V sometimes feels as if it is GTA IV but more refined and with a few new novel ideas thrown in to spice up game play. Could GTA VI possibly bring an even larger more interactive world to it? Would that even be considered fun at that point? Mayhaps a new locale or a new focus for the characters instead of the usual, albeit very entertaining, mayhem? Only time will tell, and for the foreseeable future it seems that they are committed to supporting the online gaming experience fully until the next game is even announced.
ASUS Introduces the ROG Swift PG32UQ Gaming Monitor
Evan Federowicz • Jan 13
Genesis Introduces the Rhod 250 Gaming Keyboard
Acer Announces A 4K UHD Gaming Monitor With HDMI 2.1 Support
Evan Federowicz • Jan 7
Mad Catz Introduces the R.A.T DWS Gaming Mouse
Genesis Announces The HOLM 510 RGB Gaming Desk
Evan Federowicz • Dec 31

redpajama_set_name: RedPajamaCommonCrawl


text:
MEET THE DRIVERS
OUR BOWLS
About Biased
Thank you for taking some time to read about why Biased Bowls was created. I am passionate about all sports, but bowling has become my go-to sport for so many reasons. My only regret is the perception I had about it being played by only the older generation, which has denied me decades of the sport I now love so much.
The football changing room banter, the mental battle of marathon running, or the drama of having to make a six-footer on the 18th green to win a golf match are all experiences I thought could not be achieved at bowls. How could these emotions be available on a bowls green?
Sure, bowls can be as sedate or as social as you wish. But if you have more of a competitive edge, representing your club in local leagues will give you a taster of the competitive nature within the game.
I soon had the bug and found myself entering all manner of competitions. Trust me, if you manage to play in a group game within your county, the changing room banter is fantastic. Not to mention the drama on the green, which is as tangible as any sports experience I have had.
Talent, of course, could take you further. So if you have dreams of representing your country in the sport maybe Bowls is your route. You'll never know unless you try. But don't wait! You're never too young for this wonderful game.
Becoming so enthusiastic about the game I also had a vision of how the sport could evolve further. By entering the industry my main aim is to ensure the game of bowls is experienced by all, regardless of Age, Sex, Race or Disability.
After researching the four manufacturers that are currently producing bowls, my first choice soon became apparent. Recognised for producing the most innovative and advanced bowls in the world, the choice of Taylor Bowls as manufacturers was obvious.
A meeting was then arranged to discuss the concept of a new brand entering the bowls world. A huge amount of work has been undertaken since that first meeting but thankfully all the engineering and testing has paid off! Biased is readying to enter the 21st century and beyond and with Taylor Bowls input, to drive the future innovation of its brand!
Paul Hubert
Founder – Biased Bowls
The team at Biased are hugely enthusiastic. Their desire for perfection is something we admire, understand and can accomplish. As we have a shared philosophy we have partnered with them and look forward to a positive future.
Grant Heron
Managing Director – Taylor Bowls
EMAIL: info@biasedbowls.com
PAYMENTS & SHIPPING
Biased Bowls Ltd. All rights reserved


Grate margarine in a deep dish, add milk, yeast, salt, sugar, vanilla, sift all flour into the same dish, make a dough, and place in a refrigerator for 2 hours.
Pre-heat an oven to 200 - 220 C (400 – 420 F).
Divide the dough into 1/8 lb pieces, roll every piece into a circle shape, sprinkle with sugar in the middle, and fold twice.
Press this side with a fork, dip this piece into the egg white, then roll it in sugar, and place on a baking dish.
Place the baking dish in the oven, and bake for about 20-25 minutes.
The cookies have to be layered like turnover pastry.


text:
Q: Using app:elevation in code - Android I'm trying to set the elevation of a AppBarLayout via code. When I do app:elevation in the XML it works without a hitch, however when I do
appBarLayout.setElevation(0);

It doesn't work.
My assumption is its calling the equivalent of android:elevation.
Any ideas?

A: I dont know which api version you are using , but at least you must use Api v21 to set elevation. If you set elevation in pre lolipop you should get an error , but use it like that :
if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.LOLLIPOP) {
       appBarLayout.setElevation(0);
    }

If you use it on below v21 you get this error :
FATAL EXCEPTION: main
java.lang.NoSuchMethodError: android.support.design.widget.AppBarLayout.setElevation

The result :

redpajama_set_name: RedPajamaStackExchange


Celia Gomez edited scenes from The Simpsons side-by-side with the movies those scenes are paying homage to and it's just so much fun. We get to see how the hilarious animators of The Simpsons have repurposed and refashioned those iconic movies to be set in Springfield.
That means seeing our favourite characters on The Simpsons turn into set pieces on movies like Raiders of the Lost Ark or become Sharon Stone in Basic Instinct or see how two cupcakes can be creatively used to recreate a NSFW scene in The Clockwork Orange.


A global manufacturer of papermaking machines needed a reliable coupling solution for a customer's machine rebuild/upgrade in Brazil. The OEM wanted to avoid using lubricated couplings that can generate undesired backlash. Approximately 25 electric motor-driven rolls move the paper web through the machine. Long couplings are required since the motors are positioned away from the machine to prevent damage to the electrical systems that can be caused by the steam used to dry the paper.
After considering a competitor coupling manufacturer, the OEM's Brazilian office contacted Lamiflex based on many previous successful coupling installations on papermaking machines throughout South America and around the world. Lamiflex engineers worked closely with the OEM's drivers and rolls engineering team to design cost-effective, custom PWF Series (Powerflex) disc couplings that met the machine's specific drivetrain operational conditions.
Lamiflex supplied smaller PWF couplings with standard DBSE for use on the drivetrain's high- speed side, between the electric motors and speed reducers. 4100 mm (13.4 ft.) long couplings were supplied for installation on the low-speed side, between the gearbox and machine's rolls. All couplings were custom engineered for reduced mass, adjusted for natural drivetrain frequency, and had special anti-corrosion paint applied. Low cost PWF couplings feature simple construction and high misalignment absorption capacity. Units are easy-toassemble and maintain. The longer couplings were dynamically balanced and a Lamiflex service team was on-site during drivetrain commissioning.
The end user was extremely pleased with the new Lamiflex couplings' performance and reliability and has specified them as standard for all other machines at their facilities.


text:
package com.facebook.infrastructure.db;

import java.io.Serializable;
import java.util.Comparator;

/**
 * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com ) & Karthik Ranganathan ( kranganathan@facebook.com )
 */

public class ColumnComparatorFactory
{
	public static enum ComparatorType
	{
		NAME,
		TIMESTAMP
	}

	private static Comparator<IColumn> nameComparator_ = new ColumnNameComparator();
	private static Comparator<IColumn> timestampComparator_ = new ColumnTimestampComparator();

	public static Comparator<IColumn> getComparator(ComparatorType comparatorType)
	{
		Comparator<IColumn> columnComparator = timestampComparator_;

		switch(comparatorType)
		{
			case NAME:
				columnComparator = nameComparator_;
				break;

			case TIMESTAMP:

			default:
				columnComparator = timestampComparator_;
				break;
		}

		return columnComparator;
	}

	public static Comparator<IColumn> getComparator(int comparatorTypeInt)
	{
		ComparatorType comparatorType = ComparatorType.NAME;

		if(comparatorTypeInt == ComparatorType.NAME.ordinal())
		{
			comparatorType = ComparatorType.NAME;
		}
		else if(comparatorTypeInt == ComparatorType.TIMESTAMP.ordinal())
		{
			comparatorType = ComparatorType.TIMESTAMP;
		}
		return getComparator(comparatorType);
	}

	public static void main(String[] args)
	{
		IColumn col1 = new Column("Column-9");
		IColumn col2 = new Column("Column-10");
		System.out.println("Result of compare: " + getComparator(ComparatorType.NAME).compare(col1, col2));
	}
}

abstract class AbstractColumnComparator implements Comparator<IColumn>, Serializable
{
	protected ColumnComparatorFactory.ComparatorType comparatorType_;

	public AbstractColumnComparator(ColumnComparatorFactory.ComparatorType comparatorType)
	{
		comparatorType_ = comparatorType;
	}

	ColumnComparatorFactory.ComparatorType getComparatorType()
	{
		return comparatorType_;
	}
}

class ColumnTimestampComparator extends AbstractColumnComparator
{
	ColumnTimestampComparator()
	{
		super(ColumnComparatorFactory.ComparatorType.TIMESTAMP);
	}

	/* if the time-stamps are the same then sort by names */
    public int compare(IColumn column1, IColumn column2)
    {
    	/* inverse sort by time to get hte latest first */
    	int result = column2.timestamp() - column1.timestamp();
    	if(result == 0)
    	{
    		result = column1.name().compareTo(column2.name());
    	}

        return result;
    }
}

class ColumnNameComparator extends AbstractColumnComparator
{
	ColumnNameComparator()
	{
		super(ColumnComparatorFactory.ComparatorType.NAME);
	}

    /* if the names are the same then sort by time-stamps */
    public int compare(IColumn column1, IColumn column2)
    {
    	int result = column1.name().compareTo(column2.name());
    	if(result == 0)
    	{
    		/* inverse sort by time to get hte latest first */
    		result = column2.timestamp() - column1.timestamp();
    	}

        return result;
    }
}

redpajama_set_name: RedPajamaGithub


text:
Q: What are some alternatives to interceptors in Spring 5 Webflux? I am trying to intercept my request after it enters my request controller during some of my business logic using spring webflux which is asynchronous. I know previously I could use method interceptors in spring 4 which, but what would be the alternative in spring webflux?
I was thinking about filters, but I would want to intercept the request after it has entered my controller not before.


text:
Will Jackson
Journalist and storyteller
All posts by Will Jackson
Magistrate lifts veil on vicarious trauma and PTSD in the judiciary
October 26, 2017 UncategorizedWill Jackson
Lismore Magistrate David Heilpern. TJMF
A NSW North Coast magistrate has lifted a veil of secrecy and spoken of his personal struggles with the debilitating effects of the "vicarious trauma and PTSD" suffered by members of Australia's judiciary .
In a speech at the Tristan Jepson Memorial Lecture held at the Federal Court in Sydney on Wednesday evening, Lismore Magistrate David Heilpern revealed he had himself suffered mental health issues after working on particularly affecting cases in difficult circumstances.
He cited the pervasive nature of photo and video recordings capturing graphic evidence that must be viewed by the courts as an added and significant psychological burden
Magistrate Heilpern – who explicitly made clear he was speaking for himself and not the magistracy – argued that for the good of the community more needed to be done to address the mental health of the judiciary.
"It is certainly not my intention to become some sort of poster boy for vicarious trauma or PTSD and the judiciary," he wrote in a paper accompanying the speech. "Nor can I remain silent. I am convinced that it is time to lift the veil for the benefit of the judiciary, but also for the system of justice itself. The community is best served by recognising and acknowledging this issue, rather than hiding it."
Magistrate Heilpern, a well-known progressive and self-described Buddhist and teetotaller, said the issue had been historically kept hidden, referred to euphemistically as "judicial stress".
"We ought to stop talking of 'judicial stress', and start calling it for what it is – anxiety, panic attack, insomnia, traumatic response, depression, substance abuse disorder and the like."
While there had been few studies into the problem among magistrates and judges, with research showing mental health episodes to be common among Australians and especially so among solicitors and barristers, he said "it would be a reasonable conclusion that a significant number of judicial officers suffer from debilitating mental health issues during their time on the bench".
"There is a veil based on assumptions regarding judicial officers," he said. "The sooner the veil is lifted, the sooner judicial officers can admit to difficulties, access help and better serve the community."
A former criminal lawyer and legal academic, Magistrate Heilpern joined the judiciary 18 years ago and is now a leading judicial educator in Australia and overseas.
After first paying tribute to those who suffer direct trauma from crime – the victims and first responders and also legal practitioners – he went on to detail two personal examples where his mental health suffered during his time on the bench.
The first was about 12 years ago when he found himself working on a series of child pornography cases in Batemans Bay. At the time, the court was required to view pictures and video to determine the seriousness of charges which is no longer always the case.
"I dealt with over a dozen of these cases within a couple of months," he said. "I started dreaming of these children and the torment perpetrated upon them. I would wake up in the witching hour screaming, sweating and panicked. I thought it would pass, but it did not. I was pretty scared about going to sleep, and that fear was well placed."
The nightmares only ceased after Magistrate Heilpern sought permission to avoid child pornography cases for a time and received help from the newly formed NSW Judicial Assistance Program.
He also talked of a second disturbing time during which he dealt with a particularly horrific child abuse case, a series of violent incidents inside his court, another child pornography case, and the death of friend in a surfing accident.
He found himself in a state of "hyper-vigilance" in which he was nervous for his own and family's safety.
"I found making hard decisions in court really painful. Actually physically painful – my head would hurt (just like Winnie the Pooh) when trying to decide whether to imprison someone or refuse them bail, or admit evidence. A good night's sleep had become a distant memory. I would wake myself up screaming."
Despite urging from friends and family, he felt that his reaction was "pathetic" in comparison to the victims and saw it as a matter of pride not to take time off. However, after three months, on the advice of his GP, he took a couple of weeks off, went on a Buddhist retreat and underwent therapy including Eye Movement Desensitisation Reprocessing, which he found useful.
"I approach my ability to cope with traumatic cases with a mixture of confidence and trepidation. Did it affect my ability to competently do my job during my darkest days? It is difficult to tell," he wrote. "Certainly, there was no rash of appeals from my decisions or criticism by higher courts. There were no complaints to the Judicial Commission. I probably consulted with my colleagues on harder cases to check I was on the right path and perhaps I was gruffer than usual with lawyers who I perceived as incompetent or worse."
Magistrate Heilpern said he now was alert to "soaking up" too much trauma before seeking help.
In his paper, he cited other issues such as decision makers being forced to get inside the heads of victims and perpetrators, judicial officers' intense workloads, isolation, security threats and an expectation that judicial officers would suppress emotion.
"Modern technology has made the trauma much more 'in your face'," he wrote. "Real violence is now captured on CCTV, smart-phones, in-car-videos and DVEC's. When I started in this job, some form of graphic video or photographic evidence was a rarity. Now there are few cases without it."
He said he had put in place protocols to "protect himself and his staff as much as possible" such as sealing on-scene files from coronial cases in envelopes to limit accidental exposure..
Magistrate Heilpern also discussed the fact that disclosing mental health issues could result in legal sanctions despite apparent community acceptance of the problem.
He encouraged future research to focus on the frequency of mental health issues and the profession's risk factors, the relationship between mental health and disciplinary matters, whether mental health check-ups should be undertaken and what options, such as treatment or case selection, could help those at risk.
And he finally called for the adoption of the guidelines advocated by the Tristan Jepson Memorial Foundation, which seeks to "decrease work-related psychological ill-health in the legal community and to promote workplace psychological health and safety".
"In my view, the bench should lead by example in the area of mental health," he wrote. "We are blessed by incumbency, security of tenure and status absent for many in the private profession, and those benefits should provide a firm basis for making a safe workplace."
Journalists and human rights observer attacked in crackdown on peaceful protests
September 23, 2013 Articlesbreaking news, cambodia, wat phnomWill Jackson
Note: This is all taken from Twitter reports from the scene. For more breaking news, analysis and commentary follow Will Jackson.
A human rights observer and journalists were tasered by electric prod, baton and slingshot wielding "thugs" overnight as police smashed a peaceful hunger strike protest at Phnom Penh's Wat Phnom . Continue reading Journalists and human rights observer attacked in crackdown on peaceful protests →
QnA with Hun Sen's Eye
September 21, 2013 Interviewscambodia, hun sen, politics, QnA, twitterWill Jackson
Trippin' Like a Moose. Credit: Hun Sen's Eye
Cambodia's Prime Minister Hun Sen may not be well known for his sense of humour, but his one remaining eye is undoubtedly funny as a clown in a box full of a scorpions. Since 2011, Hun Sen's Eye's Twitter feed (and later Tumblr) — poking fun at Cambodia's opposition, riffing on his sons' rampant libidos or joking about land-grabbing, torture and Johnny Walker— has given some much-needed levity to the running social media commentary on Cambodian politics, society and events. After recently topping 2000 Twitter followers, the eye was good enough to answer a few quick questions via email, delving a little deeper than 140 character tweets and picture memes usually allow.
Tell me a little bit about yourself. When did you become sentient? What's day-to-day life like for Hun Sen?
I can't really pin a date on it. A couple of years ago I noticed that everybody and their fucking cow liked to talk about the artificial eye with whom I share a skull, and it pissed me off! Why should that eye get all the press, all the fame, all the attention? Luckily, social media was there for me, starting with MySpace. LOL MySpace. It's the Funcinpec of social media.
Continue reading QnA with Hun Sen's Eye →
Khmer Rouge Tribunal limping on without Cambodian staff
September 18, 2013 Articlescambodia, Khieu Samphan, khmer rouge, khmer rouge tribunal, nuon chea, strikeWill Jackson
Note: Before I could get this article published the UN went and decided to loan the Cambodian government enough cash to pay the outstanding salaries owed to the court's Cambodian workers so I figured I might as well put it up here. A press release about the loan can be found here.
Cambodia's troubled Khmer Rouge tribunal is managing to limp toward a verdict in the first "mini trial" of "brother number two" Nuon Chea and head of state Khieu Samphan, despite ongoing strike action by 134 of the court's operational staff.
Even as the deadline for final submissions in Case 002/01 is pushed back again to September 26, the court is marshalling its remaining resources to keep work underway.
But questions remain as to how long it can continue without the Cambodian audio/visual, IT, legal support, cleaning and security staff, translators and interpreters who are refusing to come to work.
Continue reading Khmer Rouge Tribunal limping on without Cambodian staff →
Post-election protest social/traditional media mashup timeline
September 18, 2013 Articlescambodia, election, hun sen, protest, sam rainsyWill Jackson
Military Police face off with protesters during three days of post-election protests in Phnom Penh. Credit: Will Jackson
Note: This is intended to be an organic document. Any corrections or suggestions for additional material – videos, pictures, articles – are welcome. It's also a bit of an experiment. Please let me know what you think in the comments at the bottom.
It could have been any Sunday morning in Phnom Penh. Motodops hustled, food cart vendors hawked, homeless kids scrounged, women cooked and gossiped, men gambled and gossiped. The sun was out but there was a storm on the way. Standard. There was just the small matter of the razor wire everywhere. And the soldiers.
Continue reading Post-election protest social/traditional media mashup timeline →
Cambodian elections blood-free… so far
July 26, 2013 Articlescambodia, elections, hun sen, politics, sam rainsyWill Jackson
Hun Sen at the World Economic Forum on East Asia 2010. Copyright World Economic Forum/Sikarin Thanachaiary.
Cambodia will go to the polls on Sunday after what looks like being the most peaceful and relatively straightforward election campaign the troubled Southeast Asian nation has ever seen. But by no means is this a sign the country's "strongman" Prime Minister Hun Sen is relaxing his grip on power. Quite the opposite.
Ruthless and wily, Hun Sen is a classic – almost Bond-esque – villain. A former Khmer Rouge commander who lost his left eye to shrapnel during the battle for Phnom Penh in 1975, he defected to Vietnam two years later when it looked like he might become a victim of the genocidal regime's murderous paranoia – then marched back in with the Vietnamese as they booted Pol Pot out of the capital in 1979. He was installed by the Vietnamese as prime minister in 1985 and has ruled the country with a lock-jaw grip on power ever since.
Now nearly 30 years later and Asia's longest-surviving prime minister, Hun Sen remains happily ensconced in his multi-million-dollar mansion, complete with a helipad on the roof and located on the most prominent corner in Phnom Penh, and says he is determined to remain in situ for at least another decade or so. For the good of the country.
Continue reading Cambodian elections blood-free… so far →
Magistrate lifts veil on vicarious trauma and PTSD in the judiciary October 26, 2017
Journalists and human rights observer attacked in crackdown on peaceful protests September 23, 2013
QnA with Hun Sen's Eye September 21, 2013
Khmer Rouge Tribunal limping on without Cambodian staff September 18, 2013
Post-election protest social/traditional media mashup timeline September 18, 2013
You can follow Will Jackson on Twitter or contact him via email at will@willjackson.com.au.


Solid laminate table top for bar or restaurants, 12 mm thickness.
Available in cement colour, with inclined, flat or round edge.
Offered in round, square or rectangular version, in different sizes starting ∅ 59 cm.


The vector stencils library "Winter Olympics pictograms" contains 29 pictograms and silhouettes: Olympic rings, Olympic torch, medal pedestal, gold medal, silver medal, bronze medal, medals with ribbon, skis, ski poles, biathlon rifle, snowboard, ski goggles, ski gloves, ice hockey helmet, hockey stick, hockey puck, ice hockey skates, ice skates, luge, bobsleigh sled, curling stone, mountains, snowflake, fir-tree, ski lift.
Use it to create your own winter sports diagrams, infographics and illustrations.
The vector stencils library "Winter Olympics" contains 14 clipart images of Winter Olympics sports.


I think this is the most expensive lipstick I own. Even the Chanel and Guerlain ones I own do not cost more than Rs.3000. This one costs a whopping Rs.3,300. I was still contemplating my decision when I was standing in the queue to pay for my stuff and thought of buying a foundation instead. But I finally just went ahead and decided to see if it's totally worth the cost or not. The curious mind of a beauty addict!
Our boldest, most vibrant colour ever. This sumptuous formula dramatically boosts moisture levels while intensely rejuvenating lips, keeping them comfortable and conditioned—even after it's removed. Now in 30 shades, with a sleek gold tube. It's luxury, redefined.
Intensely rejuvenates lips, helping to visibly reduce the appearance of lip lines and relieve lip flaking. Plus, just one swipe delivers maximum-coverage colour.
As you can see, the packaging is beautiful! Bobbi Brown luxe lip color Pink Buff comes in a metallic golden packaging with the logo etched on the top of the cap. The shade name is written at the bottom of the lipstick. The inner tube is black in colour. Weight-wise, it's quite heavy. I actually like that because it does really gives a luxe feel! Also, the cap shuts down securely each time.
The formula of this lipstick is incredibly smooth and therefore, glides on the lips effortlessly. I find it so moisturizing and hydrating that I don't even need a lip balm. I was amazed to see that even though it's so creamy yet it never travelled past my lips or settled into lip lines. Although the true test will be when winters arrive. Also, will you believe me if I told you that it delivers full coverage in just one swipe? Yes!
Bobbi Brown luxe lip color Pink Buff is a gorgeous warm brown on my skintone. It feels extremely comfortable as long as it's on my lips. Owing to its creamy texture, it doesn't survive meals. It's not an issue with me as I'm not a fan of very long stay lipsticks on an everyday basis. On its own, it can survive for more than five hours although the color intensity has gone down.
However, the one thing I'm disappointed with it is the manner in which it fades. Given the price, I expected it to fade evenly. So, that's a major let-down for me.
Bobbi Brown luxe lip color Pink Buff is a beautiful brown on my NC30 skin tone and makes for a pretty everyday lip colour. It doesn't emphasize lip lines, goes on smoothly and feels very light-weight for its moisturizing ability. My only disappointment is that it fades unevenly. At this price, I want nothing but the best!
Have you tried Bobbi Brown luxe lip color Pink Buff or any other shade from this range? How was your experience?


text:
Health questionHealth & wellbeing
How can I cope with crippling migraines?
The attacks began when he was in his forties, and now they're getting worse. At their most violent they're beyond the reach of medication. Can anything else help?
Sat 23 Sep 2006 19.38 EDT
I'm a 50-year-old man. In my mid-forties I started suffering from migraines. Now, as I get older, they are getting more intense, though thankfully less frequent. The attacks can be quick and over in a day, or they can start slowly with nausea and vomiting and then build up over two to four days, reaching a debilitating intensity with headaches which range between slight spasms through pains which feel like my head is in a vice, to sensations like being stabbed in the head with burning needles. The attacks are always accompanied by flashing lights. In the extreme cases, even medication can't deal with the symptoms. The attacks don't seem to be connected with diet. What can I do?
Anne MacGregor
First get the diagnosis confirmed by your GP. People usually start getting migraines in their teens or early twenties, so your symptoms are unusual. If it is migraine, there are simple ways to make your medication more effective. Keep a record of your attacks to establish patterns or triggers. Always carry at least one dose of your medication and take it as soon as you feel an attack coming on - the earlier you catch it, the less intense it will be, and 900mg of soluble painkiller dissolved in a fizzy drink to help it absorb faster can be very effective.
If this doesn't work, go to your GP for something stronger: some medications can be taken daily to stop migraines developing. Vitamin B2 (riboflavin) and acupuncture have been shown to help with certain triggers. Tap into the support and information on sites such as www.migraine.org.uk and www.migrainetrust.org. If you're still not getting the help you need, ask your GP to refer you to a specialist neurologist.
· Dr Anne MacGregor is director of clinical research at the City of London Migraine Clinic (www.colmc.org.uk)
The support worker
Lee Tomkins
Migraine is a complex neurological condition, which (as in your case) can evolve. Successful management may require a combination of approaches, but lifestyle changes can make a difference. You can reduce the frequency and severity of attacks by identifying and avoiding triggers, which aren't just food-related - dehydration, low blood-sugar, bright light, loud noise, strong smells, stress, travelling (especially by air), changes in sleep patterns, smoking or stuffy rooms, working at a VDU without breaks and weather conditions can all have an adverse effect.
Luckily, many are relatively easy to deal with. Drink two litres of water every day, eat little and often (never go without food for longer than four hours during the day, or 12 hours overnight), take fresh air and gentle exercise every day, use relaxation techniques to reduce stress, wear sunglasses or a hat in bright light and keep a regular sleep pattern to protect yourself as much as possible.
· Lee Tomkins is chairman of the Migraine Action Association (www.migraine.org.uk)
The acupuncturist
Angela Hicks
Research has clearly demonstrated the benefits of acupuncture to migraine sufferers. A recent study on more than 400 patients found those who had acupuncture experienced 23.4 fewer days of migraines or headaches per year, as well as improved energy and overall health; they also used less medication and made fewer visits to GPs. Most of your symptoms, including the nausea, vomiting, visual symptoms, spasms and pains, indicate that you have imbalanced liver and gall bladder energy pathways.
This type of migraine may be made worse by long working hours, stress and frustration. An acupuncturist will discuss lifestyle changes that will help. The treatment will also help you relax. The liver and gall bladder pathways run between the head and feet, so your acupuncturist might use points on your feet. To find an acupuncturist, contact the British Acupuncture Council on 020 8735 0400 or www.acupuncture.org.uk.
· Angela Hicks is joint principal of the College of Integrated Chinese Medicine, Reading
· If you have a health question for our experts, email health@observer.co.uk
Health question


What's better than a pair of stylish sandals to add a feminine touch to every outfit? From John Galliano, we love this pair. This creation has a leather upper and leather sole. So comfortable, these shoes combine the advantages of a leather insole and a leather lining. Reach new heights with its fashionable high heel!