\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