\magnification=\magstep1
\documentstyle{amsppt}
\NoBlackBoxes
%\pagewidth{6.6truein}
%\pageheight{9.2truein}
%\vcorrection{-0.2truecm}
%\hcorrection{0.4truecm}
\parindent=12pt
\font\bigrm=cmbx10 scaled\magstep3
\font\normalrm=cmbx10 scaled\magstep2

\def \today {\ifcase \month \or January\or February\or
  March\or April\or May\or June\or July\or August\or
  September\or October\or November\or December\fi\
  \number \day, \number \year}

\def\sqr#1#2{{\vcenter{\vbox{\hrule height.#2pt
              \hbox {\vrule width.#2pt height#1pt \kern#1pt
              \vrule width.#2pt}
              \hrule height.#2pt}}}}
\def\square{\mathchoice\sqr56\sqr56\sqr{2.1}3\sqr{1.5}3}
\redefine \qed{$\square$}
\define    \qued{\text{\,\,\qed\,\,\,}}
\define\({\left(}
\define\){\right)} 
\redefine\Cup{\bigcup}

\topmatter
\title
\nofrills{\bigrm Separation of points \\ \\
\bigrm by congruent domains}
\endtitle
\author
Tibor \'Odor
\endauthor
\rightheadtext\nofrills{\sevenrm 
               Separation of points by congruent domains
}
\leftheadtext\nofrills{\sevenrm Tibor \'Odor}
\address
Math.\ Inst.\ of the Hung.\ Acad.\ of Sci., P.O.B.\ 127,
Budapest, H-1364 Hungary
\endaddress
\email
odor\@math-inst.hu
\endemail
\thanks
Research of the author in part supported  by OTKA number F4427
\endthanks
\date
\today
\enddate
\subjclass
52C20, 52C22
\endsubjclass
\keywords
scissor division, fundamental domain
\endkeywords
\abstract
In this article we investigate how we can divide balls or spheres
into congruent domains (by scissor) if we want to separate a given
finite point set.  We formulate  conjectures about the
characterization of divisions of balls into congruent domains (by
scissor).
\endabstract
\endtopmatter
\document
 
\redefine\int{\operatorname{int\,}} 
\vskip .4cm
\heading   
                            1.\ Introduction
\endheading
\vskip .2cm

\redefine\ang{\sphericalangle}
\redefine\int{\operatorname{int\,}}

As usual $D^d=\{x\in R^d:\,|x|\le1\} $ and $S^{d-1}=\{x\in
R^d:\,|x|=1\}$ denote the unit ball and  the unit sphere,
respectively,   and  $O$ is the origin in the $d$-dimensional real
vector space $R^d$, where $|\,.\,|$ is the norm.

We define the notion of the so called scissor division of domains 
of $R^d$ having piecewisely smooth boundary [Dubins et. al., 1963].
 
Let $M$ be the unit ball $B^d$ or the unit sphere $S^{d-1}$.
 
Let $M_i\subset M$ be connected closed sets for $i\in I$ which we
call later domains. We say that the system of domains $\{M_i:\,i\in
I\}$ is the scissor division, (or division by scissor) of $M$ if and
only if their union is $M$, their interiors are pairwisely disjoint
and pairwisely congruent, they (relative) boundary is a closed
surface in $R^d$.  We call the union of the boundaries of the domains
of the division is the boundary of the division.
 
It is clear that  the boundary of the division (by scissor) determine the 
division itself. This essentially means that we divide $M$ into domains  by
surfaces, which explains the term ``scissor division''.  
 
The main results are as follows:
\proclaim{Theorem 1}
Let $\Cal P=\{\text{ $P_0$, $\dots$, $P_{n-1}\in\int D^2$}\}$
 be a set of distinct points
which differ from the origin $O$. Assume that if the points $P_i$ and
$P_j$ have the same distances from the origin,
then the angle $\ang P_i OP_j$ is not equal to
$2\pi\cdot m/n$ for any positive integer $m$.
Then we can divide $D^2$ (by scissor) into $n$ congruent domains
such that each of them contains exactly one point of $\Cal P$.
\endproclaim
 
\proclaim{Theorem 2}
Let $\Cal P=\{\text{ $P_0$, $\dots$, $P_{n-1}\in\int D^d$  (or
$S^{d-1}$)}\}$  be a set  of  distinct points which differ from the
origin, where $d\ge 3$.  Then we can divide $D^d$ (or $S^{d-1}$) into
$n$ congruent domains (by scissor) such that each of them contains
exactly one point of $\Cal P$.		   
\endproclaim
 
These results are  special cases of a more general statement [\'Odor,
1996], which is  presented in terms of fundamental domains
of discrete isometry groups.

It would be interesting to characterize the possible divisions of
$D^d$. The following two conjecture gives
the characterization in the two dimensional case
and give an interesting property in higher dimensions.

Let $\gamma_0$ be a simple topological arc in $D^2$ with
endpoint  $O$, the other endpoint lying in the boundary of $D^2$
and the relative interior  points of $\gamma _0$ 
are in the interior of $D^2$.
Denote the rotated copy of $\gamma_0$ around $O$ through the
angle $2\pi\cdot m/n$ by $\gamma _n$ for $m=0$, $1,\dots,n-1$.
Assume that these simple arcs do not have common points except $O$.
Then these curves determine a division of $D^2$ in a natural way.
 
Let us call this type of divisions of $D^2$ the  first type division.
 
Let $Q_1,\dots,Q_6\in S^1$, where the angle
$\ang Q_iOQ_{i+1}$ is equal to $\pi/3$.
Let $I$ be a subset of the integers from $1$ to $6$ and let
$I^c$ be its complement.
 
Consider the circles with centre $Q_{i+1}$ and radius 1 for $i\in I$.
The points $S_{ij}$ divide the circular arcs
$Q_iO$ into $k+1$ equal parts, where $k$ is a fixed positive
integer and $1\le j\le k$.
We connect the points $S_{ij}$ with the points $Q_{i+1}$ 
with circular
 arcs of radius 1 in a way so that they are the rotated copies of $OQ_{i+1}$
 The points $S_{ij}$ divide the circular arcs $Q_iQ_{i+1}$
into $k+1$ equal part for $i\in I^c$.
Connect the points
$S_{ij}$ with $O$ by circular arcs which are the rotated copies of the
circular arc $OQ_i$ through the origin.
 
The system of circular arcs divides $D^2$ into $6\cdot(k+1)$ congruent 
domains (by scissor).
We call these type of  divisions  the   second type divisions.
 
Consider  again the circles with centre $Q_{i+1}$ and radius 1 for
$i\in I$.  The points $T_i$ are  the midpoints of the  circular arc
$Q_iO$.  The union of the segments $Q_{i-1}T_i$ and the  circular
arcs $Q_iO$ divide $D^2$ into 12 congruent domains (by scissor).

We call this type of  division  the third type division.

Now we can formulate our  conjectures:
\proclaim{Conjecture 1}
 There exist only first, second and third  type divisions (by scissor) of 
$D^2$ into congruent domains.
\endproclaim

\proclaim{Conjecture 2}
There is no division (by scissor) of $D^d$ for $d\ge 2$ into 
congruent domains whose boundary does not contain the origin.
\endproclaim

\proclaim{Conjecture 3}
There exist only first  second and third  type divisions (by scissor)
of $D^2$ into affine equivalent or Mobius equivalent domains.
\endproclaim

\proclaim{Conjecture 4}
There is no division (by scissor) of $D^d$ for $d\ge 2$ into affine
equivalent or Mobius equivalent domains whose boundary does not
contain the origin.
\endproclaim

Let $\Cal M$ be a division of $S^{d-1}$ into congruent 
domains (by scissor). Connecting $O$ and the points of  $\partial
\Cal M$ by segments, we get  a division $\Cal M'$ of $D^d$ into
congruent domains (by scissor) in a natural way, which we call the
natural extension of  $\Cal M$.

\proclaim{Conjecture 5}
Assume that $d\ge3$ and $\Cal N$ is a division of $D^d$ into
congruent domains (by scissor).  Then there exist a
division $\Cal M$  of $S^{d-1}$ and a homothopy
$F:[0,1]\times\partial \Cal M'\to D^d$ which leaves  the origin $O$
and the boundary $S^{d-1}$ of $D^d$ fixed, homeomorphism for every
$t\in[0,1]$, the mapping $F_0$ is the identity, the image of $F_t$ 
generates a division of $D^d$ into congruent domains (by scissor) for
every fixed $t\in[0,1]$ and the image of $F_1$  generates the
division $\Cal M'$, which is the natural extension of $\Cal M$.
\endproclaim

\vskip .2cm
\heading 
                       The proofs of the theorems
\endheading
\vskip .2cm
 
\demo{The proof of Theorem 1}
We use only first type divisions of $D^2$ in  our proof .
Fix an orientation on the plane. Let $S_i$ be the image of $P_i$
under the rotation about $O$
through the angle $2\pi i/n$.
As $P_iOP_j\ne 2\pi m/n$ for positive integers $m$,
it is clear that the points  $S_{i}$ and
$S_{j}$ are different if $i$ and $j$ are different.
Let $\Cal S=\{S_0,\dots,S_{n-1}\}$ be the set of these rotated points.
If we can find a $\gamma _0$ arc which determines a first type
division $\Cal D(\gamma_0)=\{D_i:\, 0\le i\le n-1\}$
of $D^2$ and $S_i\in \int D_0$,
then the division $\Cal D$ satisfies our assumptions, that is
$P_i\in D_i$ for $0\le i\le n-1$.
 
 
Let $Q\in S^1$ and assume that $\ang QOP_i/\pi$
is not a rational number. We produce $\gamma _0$ as a suitable
deformation of the
segment $OQ$. Without restricting the generality 
we can assume that the line $OQ$ is the first coordinate axis 
in $R^2$.
 
Let $C_1,\dots,C_{s}$ be circles with centre $O$
passing through the points $P_0,\dots, P_{n-1}$.

We labelled our circles $C_i$ 
in a strictly decreasing order of the radii 
 $\rho_1,\dots,
\rho_{s}$.
Let $\rho_0=1$ and $\rho _{s+1}=0$ and $C_0=S^1$ and $C_{s+1}=O$.
Let
 $Q_i$ denote the intersection of the circle $C_i$ and 
the segment $OQ$.


Let $\mu$ be the minimum of the difference of the consecutive radii
of our circles, that is $\mu=\min _{0\le i\le s}(\rho_i-\rho_{i+1})$.
Let $\theta$ be a fixed positive real number
 which is smaller than $\mu/4$.
 
Let $\Cal S_i=\{S_{j_1},\dots,S\sb{j_{ t_i}}\}=
\Cal P\cap C_i$
be the points in the point set $\Cal P$ which lie on the circle $C_h$.
Let relabel the points of $\Cal S_i$  by the symbols $S_{i1},\dots,
S_{it_i}$ in such a way that the angles $\ang QOS_{iu}$
for $1\le  u\le t_i$ are strictly decreasing.


To simplify notations, let $v_\rho(\psi)$ and $w_\rho(\psi)$ be 
simple curves  in a polar coordinate system with centre in the origin on
$R^1$, given by
$$v_\rho(\psi)=(\rho+\theta)-\theta\psi/2\pi\quad\text{ and}\quad
w_\rho(\psi)=(\rho-\theta)+\theta\psi/2\pi.$$

Let $v_i(\psi)=v_{\rho_i}(\psi)$ and 
$w_i(\psi)=w_{\rho_i}(\psi)$ for $1\le i\le s$ and denote
the image of them $v_i(\psi)$ and $w_i(\psi)$, respectively.

Let 
$V_i=v_i(0)$ and $W_i=w_i(0)$ be the starting point of the curves 
$v_i$ and $w_i$.
 It is clear that $V_i$ and $W_i$  lie on
 in the segment $OQ$ and their distance from the point $Q_i$ is $\theta$.

%For the seek of the simpler denotation let $V_{s+1}$ denote $O$.
It is clear that the simple arc $$\Gamma=QV_1\cup\bigcup\limits_{i=1}^{s-1}(v_i\cup w_i\cup
W_iV_{i+1})\cup W_sO$$ 
determines a division of the first type because its rotated
copies have exactly one common point pairwise, namely $O$.

We deform this curve $\Gamma $ into a simple
arc $\gamma_0$ in a way, that 
the division $\Cal D(\gamma_0)=\{D_i:0\le i\le n-1\}$ determined by it
separate the points of $\Cal P$. 
It is clear that this holds if 
$D_0$ contains the point set $\Cal S$.

Let $S_{iu}^l$ be the image of $S_{iu}$ under the rotation about $O$
 through the angle $2\pi l/n$, where $0\le u\le l_i$, $1\le i\le s$ and
$0\le l\le n-1$ and let $W^l_{iu}$ be the intersection points of the 
curve $w_i$ and the halfline $OS^l_{iu}$.

Consider the segments $S^l_{iu} W^l_{iu}$.  ``Blowing up'' (in
increasing magnitude in the index $l$) these segments for $1\le l\le
n-1$, we deformate the curves $v_i\cup w_i$ in a way that the
deformated curves ``leave out'' the points $S_{iu}=S^0_{iu}$ and the 
rotated copies (about $O$ through the angle $2m\pi/n$ for $m\in Z$)
of the ``blowed up segments'' does not intersect  each other.

Now we present this method more thoroughly. Let 
$$
\nu_0=\min_{1\le i\le s}\min_{1\le u<v\le t_i}
\min_{1\le k<l\le n-1}\left|\ang S^k_{iu} S^l_{iv}\right|
$$
be the minimum of the absolute value of the angles
$\ang S^k_{iu} S^l_{iv}$, where we note that the points 
$S^l_{i0}$ are rotated copies of $Q_i$, as defined earlier.

It is clear that $\nu_0$ is positive.
Let $$\nu=\dfrac{\min\{\nu_0,\theta\}}{16n^2}.$$

Let $F^l_{iu}$ and $H^l_{iu}\in w_i$ be points 
for $0\le l\le n-1$ and $1\le u\le t_i$ (but not for $u=0$)
in this order on the curve $w_i$, assuming that 
$\ang F^l_{iu}OS^l_{iu}=(l+1)\cdot\nu=\ang S ^l_{iu}OH^l_{iu}$.

Let $T^l_{iu}$ and $U^l_{iu}\in w_i$ be the intersection
points of the halflines $OF^l_{iu}$ and $OH^l_{iu}$
(with starting point $O$) and the curve $v_i$.

Let $\xi_0$ denote the minimum of the 
distances of the points $T^l_{iu}$, $U^l_{iu}$
and the circle $C_i$.
Because of our choice of $v_i$, $\xi_0$ is positive.
Let $\xi=\xi_0/16n$ be  a fixed number.

Let $A^l_{iu}$ and $B^l_{iu}\in w_i$ be
points on the halflines $OF^l_{iu}$ and $OH^l_{iu}$,
assuming that their distance from $O$ is 
$\rho_i+(l+1)\cdot\xi$.

 Denote $w^l_{iu}$ the arcs between the points $F^l_{iu}$ and
$H^l_{iu}\in w_i$ on the curve $w_i$. Let the curve 
$$
\tau^l_{iu}=F^l_{iu}A^l_{iu}\cup A^l_{iu}B^l_{iu}\cup
B^l_{iu}H^l_{iu}
$$ 
 be the union of three segments and let 
$$
 \sigma_i=v_i\cup \left(w_i\setminus
\Cup_{l=0}^{n-1}\Cup_{u=1}^{t_i}w^l_{iu}\right)\cup \Cup_{l=0}^{n-1}\
up_{u=1}^{t_i} \tau^l_{iu}
$$ 
 be the deformated  copy of the curve
$v_i\cup w_i$.

 It is clear that the rotated copies of the curves $\tau^l_{iu}$
about $O$ through the angle $2m\pi/n$ do not intersect each other for
$1\le m\le n-1$. Furthermore, if $k-l=m$ then the triangle
$OA^k_{iu}B^k_{iu}$ contains the rotated copy of $\tau^l_{iu}$ and if
$u\ne v$, then the triangles $OA^k_{iu}B^k_{iu}$ and the rotated copy
of $OA^l_{iv}B^l_{iv}$ have exactly one common point for every $0\le
k, l\le n-1$ and $1\le u\ne v\le t_i$.

 Let $$\gamma_0=\Cup_{i=1}^{s-1}\(\sigma_i\cup W_iV_{i+1}\) \cup
QV_1\cup W_sO$$ and let $\gamma_1$ be its rotated copy about $O$
through the angle $2\pi/n$.

 Using our previous remark it is easy to see that the  domain $D_0$
bounded by the closed arc $\gamma_0\cup QQ^1\cup \gamma_1$ contains
$\Cal S$ because the points $S_{iu}=S^0_{iu}$ lie on the left side of
the directed curve $\gamma_0$ (with starting point $O$) and lie on
the left side of the directed curve $\gamma_1$ (with starting point
$Q^1$, where $Q^1$ is the image of $Q$).

 This proves our statement. 
 \qued 

\demo{The proof of Theorem 2} 
 We will prove our theorem by induction simultaneously in the two
cases. Let $d=3$. If $\omega\in S^2$ then let $H(\omega)$ be 
the two--plane passing through the origin with normal vector 
$\omega$.
 Let $\pi_\omega$ denote the orthogonal projection to the two--plane 
$H(\omega)$. Let $\Cal P^\omega$ be the image of the point set  $\Cal
P$ under the projection $\pi_\omega$. It is easy to see that there
exists an $\omega\in S^2$ such that the distances of the points of 
$\Cal P^\omega$ from the origin $O$ are different.  Apply the
previous construction in the plane $H(\omega)$ for the disc
$H(\omega)\cap D^3$ and the point set $\Cal P^\omega$.
 
 The boundary of the division arises as the restriction of the
inverse image under $\pi_\omega$ of the boundary of the division in
the plane  $H(\omega)$ to the sets $D^3$ (or $S^2$).

 We can apply this method also for larger values of $d$ too.

 So the statement is proved.
\qed \enddemo

 \proclaim {Theorem 3}
 Let three distinct points be given in the unit disc $D^2$ an suppose
that they differ from the origin. Then we can divide $D^2$ into three
congruent domains (by scissor), such that each of them contains
exactly one of the given points.
 \endproclaim
 \demo{Proof}
 We can label the three points by $0$, $1$ and $2$ in such a way that
 if the distances of $P_i$ and $P_j$ from the origin are equal 
then $S_i=S_j$ and we can apply our method in the proof of the first theorem.
 \qed \enddemo

 \proclaim{Counterexample 4}
 There are four distinct points in $D^2$ such that there there does
not exist a first type division of $D^2$ in which every domain
contains exacly one of the given points.
 \endproclaim
\demo{Proof}
 Let $Q_1,\dots,Q_4$ be the vertices of a square in $S^1$ in this
order.  Let $P_1=Q_1/2$, $P_2=Q_3/2$, $P_3=Q_1/3$ and $P_4=Q_2/3$.

 We can not number this set in such a way that the image of $P_1$,
$P_2$ and the $P_3$, $P_4$ become equal after the rotation of the
$i$-th point.  So we can not divide $D^2$ in the desired way.
 
\vskip .4cm
\Refs
\widestnumber\key{HKMS87}

\ref \key Dubins et. al, 1963
\by  L. Dubins---M. Hirsch---J. Karush
\paper Scissor congruence
\jour Israel J. Math.
\vol 1
\yr 1963
\pages 239--247
\endref \vskip .1cm
 
\ref \key Fejes T\'oth, 1964
\by L. Fejes T\'oth
\book Regular figures
\publ Pergamon Press
\yr 1964
\endref \vskip .1cm

\ref \key \'Odor, 1996
\by T. \'Odor
\paper Flexibility of fundamental domains 
\jour (manuscript)
\endref \vskip .1cm

\enddocument 
