# Dynamical modelling and analysis of COVID-19 in India

R. Gopal1, V. K. Chandrasekar1 and M. Lakshmanan2 1Centre for Nonlinear
Science & Engineering, School of Electrical & Electronics Engineering, SASTRA
Deemed University, Thanjavur -613 401, Tamilnadu, India.
2 Department of Nonlinear Dynamics, School of Physics, Bharathidasan
University, Tiruchirappalli -620 014, Tamil Nadu, India.

###### Abstract

We consider the pandemic spreading of COVID-19 in India after the outbreak of
the coronavirus in Wuhan city, China. We estimate the transmission rate of the
initial infecting individuals of COVID-19 in India by using the officially
reported data at the early stage of the epidemic with the help of Susceptible
(S), Exposed (E), Infected (I), and Removed (R) population model, the so
called SEIR dynamical model. Numerical analysis and model verification are
performed to calibrate the system parameters with official public information
about the number of people infected, and then to evaluate several COVID -19
scenarios potentially applicable to India. Our findings provide an estimation
of the number of infected individuals in the pandemic period of time-line, and
also demonstrate the importance of governmental and individual efforts to
control the effects and time of the pandemic-related critical situations. We
also give special emphasis to individual reactions in the containment process.

###### pacs:

epidemic mathematical model,COVID-19, Governmental action

##  I Introduction

COVID-19, a disease caused by the severe acute respiratory syndrome
coronavirus 2 (SARS-COV 2), was first identified in December 2019 in Wuhan,
the capital of Hubei, China, and has since spread globally cohen . The World
Health Organization (WHO) announced COVID-19 as an international public health
emergency on $30^{th}$ January, 2020, and subsequently a pandemic on $11^{th}$
March, 2020 who . The number of patients is growing exponentially and
thousands of people are losing their lives in many a countries, almost every
day due to COVID-19 lin ; li ; fer . The complexity of the situation can be
realized from the fact that as on $15^{th}$ May, 2020 the number of
coronavirus cases worldwide has reached a staggering 46,39,427, with infected
patients being 25,64,442 and more than 3,08,810 confirmed deaths have been
reported due to this disease pop . Moreover, the outbreak has also spread to
more than two hundred countries pop  (Note added in revision: In continuation,
the number of coronavirus cases reached as 46,403,652 with currently infected
patients being 12,079,415 and 1,211,421 confirmed death cases as on 2nd
November, 2020).

Much work indicates that COVID-19 could spread from animal to human (zoonotic)
rothan . In addition, a rapid increase of COVID-19 infections show the main
finding that secondary transmission can occur through human-to-human contacts
or through droplets transmitted by coughing or sneezing from an infected
person rothan ; li  or even when an infected person speaks to a non-infected
one. With the above trend, this spread of human-to-human disease is growing
significantly almost everywhere in the world and the infection is rapidly
increasing in many countries through local transmission li .

In India, the infection due to COVID-19 was first identified on $02^{nd}$
March, 2020. The Indian Government announced a 21-day country-wide lock-down
as a preventive measure for the COVID-19 outbreak on $24^{th}$ March, 2020.
The aim of the lockdown was to slow down the spread of the novel coronavirus,
to allow the Government to follow a multi-pronged strategy to add more beds in
its hospital network, to increase the development of the COVID-19 test kits
and of personal protective equipments (PPEs) for health workers, etc. The
government frequently uses different platforms to keep the public aware of
COVID -19. In India, conditions including very high population density in
urban areas, unavailability of vaccines and inadequate data about the
disease’s transmitting process also make it a herculean task to adequately
fight the disease.

Mathematical simulations were often used to forecast the effects of various
epidemics and also to test the efficacy of the different prevention approaches
in reducing the burden of the epidemics ker . Recently, concerning the current
COVID-19 pandemic, considerable research has been carried out using actual
occurrence from the impacted countries, analyzing various aspects of the
epidemic, as well as assessing the impact of preventive approaches adopted in
order to limit the epidemic in the countries concerned arxiv . In particular,
various kinds of dynamical models have been employed, essentially considering
nonlinear governing equations. For instance, the nature of human coronavirus
infection and defining contact between human cells and the virus have been
described in Ref rihan . The statistical model for estimating virus
transmission, taking into account a condensed version of the bats-hosts-
reservoir-people transmission model, known as a reservoir-people model was
also reported in Ref chen .

Susceptible-exposed-infectious-recovered (SEIR) model is an important tool for
tackling coronavirus transmission statistical simulations. Lin and his co-
workers have proposed a method to develop analytical models for the COVID-19
outbreak in Wuhan taking into account human behavioral responses and
government decisions, such as holiday extension, travel restriction,
hospitalization, and quarantine lin . Some recent studies based on these works
use numerical simulations and attempt to provide a reliable real-time forecast
of COVID-19 cases in various countries with the help of this mathematical
model. For instance, Savi _et al_ have obtained the general transmission of
the novel coronavirus to test various scenarios of coronavirus propagation in
different countries, taking into account the model testing of the evolution of
infected populations in China, Italy, Iran and Brazil based on government and
individual reactions savi .

In this work, we consider the situation in India starting from the initial
outbreak period and fitted SEIR model to the daily infected cases reported
between $2^{nd}$ March, 2020 to $15^{th}$ May, 2020. We estimate the basic
transmission rate of COVID-19 in the initial stage of the epidemic between
$2^{nd}$ March, 2020 and $24^{th}$ March, 2020. Further, the general
propagation of the novel coronavirus is also studied in our investigation to
evaluate different scenarios of the propagation of coronavirus. In addition,
the model verification takes into consideration the evolution of the infected
population and simulates different scenarios based on the rate of transmission
and the governmental and, especially individual reactions. Finally it proposes
potential evolution of the spread and possible mitigations, specifically
emphasizing the significance of individual reactions at the societal level
during the pandemic period which includes both lock-down and various unlock
periods.

The structure of the paper is as follows. In section II, we briefly describe
the SEIR dynamical model. The estimation of transmission rate and detailed
numerical analysis of the mathematical model with actual data is described in
section III. Finally, we discuss the findings obtained from our study in
Section IV. In the Appendix (added in the revision), we also provide details
of our study on the number of infected individuals during the lock-down and
unlock periods starting from March, $25^{th}$, 2020 to October 31 2020 and
further up to December $27^{th}$, 2020.

Table 1: Summary table of the parameters discussed in Eqs. (1f) and (2) Parameter | Description | value/remarks/reference
---|---|---
$N_{0}$ | Initial number of population | India populations pop1
$S_{0}$ | Initial number of susceptible population |  $0.9N_{0}$ (constant)
$E_{0}$ | Exposed persons for each infected person |  $20I_{0}$ (assumed)
$I_{0}$ | Initial state of infected persons | 3 pop1
$\alpha$ | Government action strength | varied in each lock-down period
k | intensity of individual reaction | 1117.3 lin ; savi
$\sigma^{-1}$ | Mean latent period | 3 (days)
$\gamma^{-1}$ | Mean infectious period | 5 (days)
$d$ | Proportion of severe cases | 0.2
$\lambda^{-1}$ | Mean duration of public reaction | 11.2 (days)
Figure 1: The number of infected individuals (excluding number of initial
quarantined people) after the first few days of outbreak on $2^{nd}$ March,
2020. Data were fitted by the nonlinear least-square fit for India. The solid
black line is fitting data and red circles denote real data of the number of
infected individuals.

##  II The Dynamical model

Lin and his co-workers have proposed a susceptible-exposed-infectious-removed
(SEIR) model to explain coronavirus disease (COVID-19) lin . This model was
inspired by He _et al’s_ original influenza model he ; he1 . The SEIR model
also has two supplementary terms: $D$ is a public perception of risk with
respect to serious cases and deaths, and $C$ is the number of recorded and
unreported incidents. In addition, $S$ is the susceptible population, $E$ is
the population exposed, $I$ is the currently infectious population (excluding
the recovered and death cases) and $R$ is the population removed which
includes both the cases of recovered and deaths. The simplified version of the
governing equations takes account of the interaction between all these
populations, and is represented by the following set of coupled nonlinear
differential equations lin ,

$\displaystyle\dot{S}=-\beta(t)\frac{SI}{N},$ (1a)
$\displaystyle\dot{E}=\beta(t)\frac{SI}{N}-\sigma~{}E,$ (1b)
$\displaystyle\dot{I}=\sigma E-\gamma I,$ (1c)
$\displaystyle\dot{R}=\gamma_{R}I,$ (1d) $\displaystyle\dot{D}=d\gamma
I-\lambda D,$ (1e) $\displaystyle\dot{C}=\sigma E,$ (1f)

where $\gamma$ is the mean infectious period, $\gamma_{R}$ is the delayed
removed period, which denotes the relation between removed population and the
infected one, $\sigma$ is the mean latent period, $d$ denotes the proportion
of severe cases and $\lambda$ is the mean duration of public reaction li ; lin
; savi .

In Eq.(1f), $\beta(t)$ denotes the transmission rate function which
incorporates the impact of governmental action $(1-\alpha)$, and the
individual action, which is denoted by the function
$\left(1-\frac{D}{N}\right)^{k}$ lin ; savi . Here, the parameter $k$ defines
the intensity of individual reaction, which is measured on a scale of 0 to
$10^{5}$ with a normal value of 1117.3 obtained from previous and recent
epidemic and pandemic studies he ; lin . We also assume that the effect of
governmental action is different during different lock-down periods.
Therefore, the transmission rate $\beta(t)$ is defined as

$\displaystyle\beta(t)=\beta_{0}(1-\alpha)\left(1-\frac{D}{N}\right)^{k}.$ (2)

The value of $\beta_{0}$ is derived by assuming that the basic reproduction
number is $R_{0}=\frac{\beta_{0}}{\gamma}$, which measures the average number
of new infections generated by each infected person. The values of the system
parameters are mentioned in Table 1, based on the information deduced from the
references in he ; li ; lin ; savi ; das .

The above parameters must be modified for each state/country which is
important for the analysis of COVID-19. In general, the physical meanings of
the parameters are based on a variety of facts, identifying which constitute a
difficult task lin . It should be also pointed out in this regard that the
real data has spatial aspects that are not covered by the above set of
governing equations. Consequently, this kind of study is a sort of average
activity that needs careful adjustment to suit real data as followed by
earlier studies lin ; savi .

In our present study, we use step-like functions to define certain parameters
that allow for a proper representation of different scenarios, especially the
rate of transmission. It is also important to remember that all governmental
or individual decisions have a delayed impact on the dynamics of the system.
Further, virus mutation is another important factor related to the definition
of COVID-19 dynamics which can affect the reaction of the system significantly
but is not discussed in our present study savi . The next sections treat the
COVID-19 dynamics considering two different objectives. To start with, we
identify the initial value of transmission rate with the data from initially
infected people, and then it examines various scenarios for the COVID -19
situation in India, using different transmission rates and government and
individual action strengths.

Figure 2: Variation of transmission rate considered in our model (1f), through
time with the impact of $\alpha$ in (2) with respect to initial transmission
value $\beta_{0}=0.56$. The continuous curve is for intensity of individual
reaction $k=1117.3$ and the dotted curve is for $k=0$. Figure 3: Numerical
simulation of the number of infected individual people (excluding both
recovered and deaths) with the value of initial transmission rate taken as
$\beta_{0}=0.56$ and for different governmental action strengths before and
after the lock-down period. The prediction of the mathematical model
(continuous blue and black curve) compared with actual data (red dotted curve)
for the daily infected people in India upto (a) $3^{rd}$ May, 2020 and, (b)
$17^{th}$ May, 2020 is depicted. The strength of individual reaction is
considered as $k=1117.3$ and the remaining parameters are taken from Table 1.

##  III Data analysis with numerical model

As a first phase of the established study, model verification is performed
using information available on India covid-19 tracker and worldometers.info
pop . We follow the SEIR implementation methodology described for various
countries in savi . The model employed for simulations is with a total
population of India at $N\approx 139\times 10^{7}$ pop1 , and 3 infected
COVID-19 confirmed as on 02-Mar-2020. The initial state is taken to be with
$I_{0}=3$ and a susceptible initial population is assumed to be $S_{0}=0.9N$.
Another information needed for the model is the number of individuals exposed
to each infected person. Each infected individual is believed to have the
potential to infect a further 20 individuals, $E_{0}=20I_{0}$ lin ; savi .
Initially, we started with the estimation of the initial transmission rate.

###  III.1 Estimation of initial transmission rate

To start with, we note that, intensified precautionary measures to curb the
spread of COVID -19 was carried out in India. In particular, when patients
were found at a location, the Committee of Physicians and Experts checked
those people who had contacts with the patients. After that, both the patients
and the contaminated people were quarantined in a hospital or in other
isolated areas. In India’s data published, in the initial few days, the active
cases were automatically moved to quarantined cases gov . Therefore, the
active cases correlate after a few days with the omitted quarantined cases.
From the recorded data we can match real infected individuals (excluding
quarantined people) as a function of time at the early stage of the disease
spreading bar the initial quarantined people chae .

In order to solve the model (1f), we consider the susceptible population to be
close to the overall population in the early stages of transmission of the
disease chae , and we can rewrite the dynamic equation of the epidemic with
$\frac{S}{N}\approx 1$.

In this case, from Eqs. (1c) and (1b), the equation for the presently
infectious population (which excludes the recovered and death cases) becomes
the second order linear ordinary differential equation of damped linear type,

$\displaystyle\ddot{I}+(\gamma+\sigma)\dot{I}-\sigma(\beta-\gamma)I=0.$ (3)

By integrating the above equation, we obtain the solution as lak

$\displaystyle
I(t)=I_{01}e^{\frac{-1}{2}(\gamma+\sigma-\sqrt{(\gamma-\sigma)^{2}+4\sigma\beta})t}+I_{02}e^{\frac{-1}{2}(\gamma+\sigma+\sqrt{(\gamma-\sigma)^{2}+4\sigma\beta})t},$
(4)

where $I(0)=I_{01}+I_{02}$ is the initial number of individual infected
people. Now the curve is fitted with the initial real infectious population
data available in pop . Further we identify an exact fit with the curve
$3e^{0.473t}$. From this we obtain the parameter values as $I_{01}=3$,
$I_{02}=0$ and the initial value of $\beta$ is 0.56. This $\beta$ value can be
considered as the initial transmission rate $\beta_{0}$ in (2). It gives the
reproduction number $R_{0}=\frac{\beta_{0}}{\gamma}=2.8$. One may note that a
few recent studies suggest a reproduction rate of $R_{0}$ about 2.52 for the
first 22 days before lockdown, and then identify the value of $R_{0}$ to vary
between 1.9 to 3.0 in various places in India, due to the variation of
transmission rates das ; liu ; chae , but in our analysis the estimation of
$R_{0}$ from the model is confirmed with real data of daily infected
individuals (excluding recovered and death cases). In Fig. 1 we represent the
curve fit of the infected people as a function of time at the early stage of
the disease spreading in India.

Figure 4: Numerical simulation of the evolution of number of infected
individuals with the value of initial transmission rate $\beta_{0}=0.56$. The
red curve denotes actual data for the daily infected people (excluding
recovered and death cases) in India up-to $15^{th}$ May, 2020. Note that this
simulation (See column IV) shows the rate of newly infected population after
May 3 with respect to the values of government action strength $\alpha$ in (2)
with (a) $\alpha=0.22$, (b) $\alpha=0.25$, (c) $\alpha=0.3$, and (d)
$\alpha=0.4$. The strength of individual reaction considered is a rather low
value of k = 1117.3 and the remaining parameters are taken from Table 1.

###  III.2 Verification through Simulations

In this section, the first scenario for model verification based on the
results of India is presented. It should be noted that our analysis considers
all infected cases in entire India, and it is not restricted to any specific
state or place. The parameters which are used in the model are specified in
Table 1, and these parameters should be treated as average since they are
appropriate for the country as a whole. Initially, we started with the value
of transmission rate starting with $\beta_{0}=0.56$ and the value attributable
to governmental action strength is also considered as different during the
periods before and after lock-down. Fig. 2 charts the transmission rate
$\beta(t)$, before and after the lock-down period with respect to various
governmental action strengths. One may note that one important constraint on
the parameter $\beta(t)$ is that this variable should be a step-like function
with time due to the impact of government action strength. Therefore, using
the daily COVID-19 incidence data, numerical simulation is carried out for the
model (2) with the value of $\beta_{0}=0.56$. Fig. 3 shows the evolution of
the number of infected individuals (excluding both recovered and death
population), indicating a strong agreement between simulation and actual data.
The infected people regions are marked as I, II,III and IV and they correspond
to the periods of Mar 02 -Mar 24 (before lock-down), Mar 25-April 14 (first
lock-down), April 15 - May 3 (second lock-down) and May 4 - May 17 (third
lock-down), respectively.

Figure 5: Numerical simulation of the evolution of the number of infected
individuals with the specific value of initial transmission rate
$\beta_{0}=0.56$, after May 3 (expanded view of column IV in Figs. 4(c)-(d))
with respect to different values of intensity of individual response $k$ in
Eq.(2) for different values of government action strength in (a) $\alpha=0.3$,
and (b) $\alpha=0.4$. The remaining parameters are taken from Table 1. Figure
6: Numerical simulation of the evolution of the number of infected individuals
for the value of initial transmission rate $\beta_{0}=0.56$ and $k=1117.3$ (I
- IV). Note that this simulation shows rate of infected people after May 17
(see column V) with respect to the different values individual reaction in Eq.
(2) with (a) $\alpha=0.3$ and (b) $\alpha=0.4$. The remaining parameters are
taken from Table 1.

It is apparent that our estimation of the number of infected individuals in
the model (1), with basic transmission rate, system parameters and different
governmental action strengths upto the end of the second lock-down period
starting from initial outbreak (Mar 2 -May 3) shows good agreement with the
actual data of infected individuals (See Fig.3(a)). This study helps to
predict newly infected individuals in the near future. For instance, we choose
low values of governmental action strengths, $\alpha=0.3$ and $0.4$, in the
third lock-down period (due to the minimum relaxation given by the government,
when certain activities were permitted and restricted in each zone) compared
to $\alpha=0.45$ during the second lock-down period, and our model study
predicts the number of infected individuals reasonably well with the real data
for $\alpha=0.4$ in the region IV (See black curve in Fig.3(b)). Note that in
Figs.3, we have also included the strength of individual reaction at a rather
low value of $k=1117.3$, see Eq. (2) above, but the contribution due to this
term is only minimal. A sample summary of the actual infected people in India
pop , and prediction of infected individuals from the model (1f) are given in
Table.2.

Table 2: Sample summary of actual data of COVID-19 pandemic in India pop  and predicted infected people (I(t)) from SEIR model given by Eqs. (1f) and (2) Date | Number of Infected People pop (worldometers) | SEIR Model (I(t))
---|---|---
04/03/2020 | 26 | 29
10/03/2020 | 58 | 84
24/03/2020 | 486 | 679
2/04/2020 | 2280 | 2249
11/04/2020 | 7189 | 7103
14/04/2020 | 9735 | 10417
15/04/2020 | 10440 | 11564
19/04/2020 | 14202 | 14660
23/04/2020 | 17306 | 17575
24/04/2020 | 18171 | 18370
25/04/2020 | 19519 | 19198
03/05/2020 | 29339 | 27261
10/05/2020 | 43980 | 43910
13/05/2020 | 49104 | 55958 ($\alpha=0.3$); 46368 ($\alpha=0.4$)
14/05/2020 | 51379 | 60668 ($\alpha=0.3$); 49073 ($\alpha=0.4$)
15/05/2020 | 52773 | 65767 ($\alpha=0.3$); 51904 ($\alpha=0.4$)

###  III.3 Role of governmental action and individual reaction

In addition, we also analyze the possibility of impact of prevention
approaches in reducing new cases infected with COVID-19 via the above
mathematical model, after $3^{rd}$ May, 2020 (For instance $4^{th}$ May, 2020
- $10^{th}$ June, 2020, and beyond, marked as region IV in Figs. 4(a)-(d)).
Strategies for prevention include preventive mechanisms such as lock-down,
information campaign by newspapers and television, adequate hand sanitation,
social distancing etc. which results in slowing down the COVID-19 transmission
process. These strategies of prevention as modeled in terms of the parameter
$\alpha$ and $k$ in Eq. (2), which imply that there will be a reduction in the
transmission rate $\beta(t)$. Now, we start with the efficiency of prevention
by varying government action strength alone, keeping $k$ at fixed low strength
$k=1117.3$ lin . For such low values of strengths, that is for $\alpha=0.22$
and $\alpha=0.25$, it is observed that the number of infected individuals will
peak around $8\times 10^{5}$ and $7\times 10^{5}$ respectively by June 10 (see
Fig.4(a)-(b)). If the strength is increased (for $\alpha=0.30$), the peak of
the infected/active people cases may decrease and the occurrence of the peak
is shifted down to $5\times 10^{5}$ on June 10 (see Fig.4(c)). Now, we
consider a further increased value of government action strength (for
$\alpha=0.4$), and the newly infected cases can decrease and reach around
$2.5\times 10^{5}$ by June 10 (see Fig.4(d)).

Analyzing the results of the above, the present dynamical model clearly shows
that when the value of $\alpha$ is reduced, new infected cases continue to
quickly increase, while a larger value of $\alpha$ decreases the infected
cases to a considerable extent. However, the later will not also help in
reducing the infection to approach zero unless perhaps $\alpha$ approaches a
value close to unity. Moreover, it is not practical to keep increasing the
governmental action to a higher and higher level even in the fourth lock-down
period and further due to the necessity of opening up the economic front for
survival of the nation. On the other hand, with relaxation of governmental
action over time, particularly in the fourth lock-down period and subsequent
period, the above type of prevention method alone will not end up in the
eradication of the disease.

In the above, in Figs. 4, we have shown our simulations, based on the various
governmental action strengths with fixed low value of intensity of individual
reaction ($k=1117.3$) in Eq.(2). Individual reactions or behavior can include
social distancing, personal hygiene, health habits and avoiding crowded places
and so on who . It will also include alerting fellow citizens to wear masks,
to follow personal hygiene and social distancing, political and social
organizations urging fellow citizens to follow social norms and so on. Now, we
also address the importance of individual reactions with low value of
governmental action strength $\alpha=0.3$ and $\alpha=0.4$ in the region V
(which corresponds to the period beyond May 18) in Figs. 5. We observe from
Figs. 5 that the number of infected people increases for no action of
individual response (for $k=0$), while the number of infected people decreases
when the value of individual response increases to $k$=3000, 5000 and 10000.
From these figures we also learn that individual behavioral responses are also
very important along with governmental action.

In the above scenario, we further considered different low values of
government action strength $\alpha$ in the region IV in Figs.4(a)-(d) (i-e May
3- June 10) and various values of intensity of individual reaction in the same
region in Figs. 5(a)-(b). The corresponding figures show that the disease
continues to infect more and more people due to low value of governmental
action strength, but it can become controllable with respect to appropriate
individual reactions. In order to break the chain of infection spread and to
get more controllable handle on infected individuals one may choose immediate
action of the individual reaction response after third lock-down period, that
is range IV, and consider appropriate values of $\alpha$ and $k$ in the time
window V in Figs. 6. For $\alpha=0.3$ or 0.4 and $k=10000$ or $k=20000$ the
newly infected cases tend to decrease within a few weeks, after May 18 (see
Figs. 6(a)-(b)). If the individual reaction is increased further ($k=30000$
and $k=50000$) we see that the disease can be effectively eradicated within 1
to 2 months from $18^{th}$ May, 2020 (see Figs. 6(a)-(b)).

Based on our analysis in Figs. 4-6, we find that if we introduce appropriate
values of individual reaction strength $k$, then even for low values of
governmental action, the reduction can become substantially impressive and one
can approach a regime of complete controlling of the disease in a reasonably
short period in the absence of appropriate vaccination and so on.

##  IV Conclusion

On $3^{rd}$ May, 2020 the total number of active infected cases registered for
COVID-19 and deceased cases in India were 29,339 and 1391, respectively and on
May $15^{th}$ they stood at 52,773 and 2753, respectively and on November 04,
2020 they stood at 5,33,787 and 1,23,611, respectively gov . This amount of
rise in the active infected cases has happened after some minimal relaxation
in the government lock-down, and several hundred new cases are reported every
day from different locations across India. Our study analyzed the effect of
lock-down days on the spread of COVID-19 disease in India. Therefore,
predictive mathematical/dynamical models can also provide useful insights to
strengthen our understanding of COVID-19 transmission and control.

In our study, we considered a dynamical model of Susceptible-Exposed-
Infectious-Removed (SEIR) spreading epidemic, and estimated the initial rate
of COVID-19 transmission by considering the initially infected people in
India. In addition, a verification procedure is also performed with respect to
different transmission rate values based on the data available from India. Our
findings also indicate that the government and in particular individual
efforts are important in reducing infected populations and also in reducing
the overall epidemic period. In addition, we would like to note that these
kind of epidemic mathematical models and their predictive simulations are also
valuable resources which can be helpful for public health planning and in
governmental as well as individual acts. Further, our study also shows that
the COVID-19 pandemic can be suppressed by a lock-down.

Our model and current data seem to indicate that the confirmed infected
individuals continue to grow in India every day, in spite of rapid response by
the government to the pandemic through various quarantine measures, nationwide
lock-down and risk-based zoning and so on when the individual reaction rate
($k$) is taken as low. But we find that for appropriate increased values of
individual reaction, even with low governmental action strength, there can be
dramatic reduction in the total number of infected people. Depending upon the
increased individual contribution the disease can be effectively controlled in
a rather short period. It is then imperative that society as a whole
contributes its might by simple social measures, besides appropriate
governmental action. These combined efforts can contribute towards a total
control of the disease in a short period in India and perhaps elsewhere as
well.

## Acknowledgements

The work of V.K.C. forms part of a research project sponsored by SERB-DST-
MATRICS Grant No. MTR/2018/000676. M.L. wishes to thank the Department of
Science and Technology for the award of a SERB Distinguished Fellowship under
Grant No.SB/DF/04/2017.

Figure 7: Numerical simulation of infected people with the value of initial
transmission value $\beta_{0}=0.56$. The red curve denotes actual data from
refs pop ; gov  for the daily infected people in India up-to Oct 31,2020. Note
that the present present simulation (I-XI column) shows the rate of infected
people in the timeline, from Mar 02,2020 to Dec 27,2020 with respect to the
various values of government action strengths $\alpha$ and individual reaction
$k$ as given in Table III. If the strength of the individual reaction $k$ is
increased further (after October 31,2020), the number of the infected
individuals may decrease and come to an end in a short period of time (black
curve in region XI).

## Appendix-I (Added in the revision)

###  IV.1 Study of infected individuals during lock-down and unlock periods

In order to get a clear insight on the estimation of our prediction, Fig. 7
shows the rate of infected individual people with respect to timeline of
various lock-down and unlock periods. It shows that various intervention
strategies (lock-down, spreading awareness program, public reaction, proper
hand sanitization, etc), including measures like governmental action strength
$\alpha$ and intensity of individual reaction $k$ play an important role in
controlling the number of infected individual people in India.

Staring from the initial date of outbreak, we consider a period of 300 days as
timeline and study the impact of various interventions during this period.
Speaking in terms of the actual dates, we consider the time period between
$2^{nd}$ March 2020 to $27^{th}$ December 2020. Our study shows that with
comparatively low values of the parameters $\alpha$ and $k$ the time of
occurrence of the peak of the outbreak happens during the unlock period Unlock
4.0, and it is represented as region IX in Fig. 7. If the strength of the
intensity of individual reaction increases further from $k$ = 2500 in region
IX to 3500 in region X and then to 6000 and then to 10000 or even 20000 in the
region XI, the number of infected individuals decreases rather quickly and can
reach a minimum at the end of December 2020 (The increased value of individual
reaction $k$ may be attributed to increased awareness among people and more
number of individuals following basic hygiene,etc..). Our results seem to
agree well with a recent COVID-19 data on India who ; gov . Further, our study
also shows that when the value of $k$ is decreased further in the forthcoming
period in the XI window region (Fig.7), the new cases tend to increase and it
will show the possibility of increased occurrence of infected individuals
rapidly (blue and pink curves in region XI).

Table 3: Values of governmental action strength $\alpha$ and, intensity of individual reaction $k$ used during No lock-down (No LD), lock-down (LD) and unlock period (UL) in Eq. (2). Phases | Timeline | Figure | Region | value of $\alpha$ | value of $k$
---|---|---|---|---|---
No LD | 02 March - 24 March |  3(b) | I | 0.0 | 1117.3
LD-1 | 25 March - 14 April |  3(b) | II | 0.1 | 1117.3
LD-2 | 15 April - 3 May |  3(b) | III | 0.45 | 1117.3
LD-3 | 4-17 May |  3(b) | IV | 0.40 | 1117.3
LD-4 | 18-31 May | 7 | V | 0.40 | 2000
UL-1 | 1-30 June | 7 | VI | 0.38 | 2100
UL-2 | 1-31 July | 7 | VII | 0.30 | 2200
UL-3 | 1-31 August | 7 | VIII | 0.25 | 2300
UL-4 | 1-30 September | 7 | IX | 0.11 | 2500
UL-5 | 1-31 October | 7 | X | 0.10 | 3500
UL-6 | 1 November- | 7 | XI | 0.10 | 6000 (blue)
|  | 7 | XI | 0.10 | 10000 (pink)
|  | 7 | XI | 0.10 | 20000 (black)

## References

  * (1) Cohen, J. and Normile, D., New SARS like virus in China triggers alarm, Science, 2020, 367, 6475.
  * (2) WHO, 2020;https://www.who.int/emergencies/diseases/novel-coronavirus-2019/technical-guid(available online).
  * (3) Lin, Q., Zhao, S., Gao, D., Lou, Y., Yang, S., Musa, S. S., Wang, M. H., Cai, Y., Wang, W., Yang, L. and Hee. D., A conceptual model for the coronavirus disease 2019 (COVID-19) outbreak in Wuhan, China with individual reaction and governmental action, International Journal of Infectious Diseases, 2020, 93, 211-216.
  * (4) Li, Q., Med, M., Guan, X., Wu, P., Wang, X. and Zhou, L., et. al., Early transmission dynamics in Wuhan, China, of novel coronavirus-infected pneumonia, The New England Journal of Medicine, 2020, 382, 1199; doi:10.1056/NEJMoa2001316.
  * (5) Ferguson, N. M., Laydon, D., Nedjati-Gilani, G., Imai, N., Ainslie, K., Baguelin, M., Bhatia, S. and Boonyasiri, A., et. al., Impact of non-pharmaceutical interventions (npis) toto reduce covid-19 mortality and healthcare demand. London: Imperial College COVID- 19 Response Team, 2020; doi: 10.25561/77482.
  * (6) https://www.worldometers.info/coronavirus/country;https://www.covid19india.org [accessed on 16 May 2020; 8:01GMT; 05 Nov 2020; 8.01 GMT];
  * (7) Rothan, H. and Byrareddy, S., The epidemiology and pathogenesis of coronavirus disease (COVID-19) outbreak, J. Autoimmun, 2020, 109, 102433; doi:10.1016/j.jaut.2020.102433.
  * (8) Kermack, W. O. and McKendrick, A. G., Contributions to the mathematical theory of epidemics—I, Bulletin of Mathematical Biology, 1991, 53, 33.
  * (9) arXiv.org,  https://arxiv.org; bioRxiv.org,  https://www.biorxiv.org.
  * (10) Rihan, F. A., Al-Salti, N. S. and Anwar, M. N. Y., Dynamics of coronavirus infection in human, AIP Conference Proceedings, 2018, 1982, 020009; doi:10.1063/1.5045415.
  * (11) Chen, T. M., Rui, J., Wang, W. P., Zhao, Z. Y., Cui, J. A., and Yin, L., A mathematical model for simulating the phase-based transmissibility of a novel coronavirus, Infectious Diseases of Poverty, 2020, 9, 24; doi: 10.1186/s40249-020-00640-3.
  * (12) Savi, P. V., Savi, M. A. and Borges, B., A mathematical description of the dynamics of coronavisrus disease (2019):(COVID-19):A case study of Brazil, 2020; arXiv:2004.03495v2.
  * (13) He, D., Dushoff, J., Day, T., Ma. J. and Earn, D. J. D., Inferring the causes of the three waves of the 1918 influenza pandemic in England and Wales, Proc. R. Soc. B, 2013, 280, 20131345; doi:10.1098/rspb.2013.1345.
  * (14) He, D., Ionides E. L., and King, A. A., Plug-and-play inference for disease dynamics: measles in large and small populations as a case study, J. R. Soc. Interface, 2010, 7, 271-283; doi:10.1098/rsif.2009.0151.
  * (15) https:www.statisticstimes.com/demographics/population-of-india.php
  * (16) Lakshmanan, M. and Rajasekar, S., Nonlinear Dynamics: Integrability Chaos and Patterns, Springer-Verlag, Berlin, 2003.
  * (17) Sourish Das, Prediction of COVID-19 Disease Progression in India, 2020; arXiv:2004.031471v1.
  * (18) Liu, Y., Gayle, A. A., Smith, A. W. and Rocklow, J., The reproductive number of COVID-19 is higher compared to SARS coronovirus, Journel of travel medicine, 2020, 1-4; doi:10.1093/jtm/taaa021.
  * (19) https://www.mygov.in/covid-19
  * (20) Chae, S. Y., and Lee, K. E., et. al., Estimation of Infection Rate and Prediction of Initial Infected Individuals of COVID-19, 2020; arxiv.org/pdf/2004.12665.
  * (21) MOHFW, Coronavirus disease 2019 (COVID-19). Ministry of Health and Family Welfare, 2020; https://www.mohfw.gov.in(available online).


11institutetext: Institute of Software Technology, Graz University of
Technology, Austria 11email<EMAIL_ADDRESS>22institutetext: IST Austria 22email:
<EMAIL_ADDRESS>33institutetext: TU Eindhoven, The Netherlands 33email:
<EMAIL_ADDRESS>
# On Compatible Matchings††thanks: A.A. funded by the Marie Skłodowska-Curie
grant agreement No 754411. Z.M. partially funded by Wittgenstein Prize,
Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V.
partially supported by FWF within the collaborative DACH project _Arrangements
and Drawings_ as FWF project I 3340-N35. A.P. supported by a Schrödinger
fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant
no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).

Oswin Aichholzer 11 Alan Arroyo 22 Zuzana Masárová 22 Irene Parada 33 Daniel
Perz 11 Alexander Pilz 11 Josef Tkadlec 22 Birgit Vogtenhuber 11

###### Abstract

A matching is compatible to two or more labeled point sets of size $n$ with
labels $\\{1,\dots,n\\}$ if its straight-line drawing on each of these point
sets is crossing-free. We study the maximum number of edges in a matching
compatible to two or more labeled point sets in general position in the plane.
We show that for any two labeled convex sets of $n$ points there exists a
compatible matching with $\lfloor\sqrt{2n}\rfloor$ edges. More generally, for
any $\ell$ labeled point sets we construct compatible matchings of size
$\Omega(n^{1/\ell})$. As a corresponding upper bound, we use probabilistic
arguments to show that for any $\ell$ given sets of $n$ points there exists a
labeling of each set such that the largest compatible matching has
$\mathcal{O}(n^{2/(\ell+1)})$ edges. Finally, we show that $\Theta(\log n)$
copies of any set of $n$ points are necessary and sufficient for the existence
of a labeling such that any compatible matching consists only of a single
edge.

###### Keywords:

compatible graphs crossing-free matchings geometric graphs

##  1 Introduction

For plane drawings of geometric graphs, the term _compatible_ is used in two
rather different interpretations. In the first variant, two plane drawings of
geometric graphs are embedded on the same set $P$ of points. They are called
compatible (to each other with respect to $P$) if their union is plane (see
e.g. [3, 20]). Note that this is different to simultaneous planar graph
embedding, as it is required not only that the two graphs are plane, but also
that their union is crossing-free.

In the second setting, which is the one that we will consider in this work,
one planar graph $G$ is drawn straight-line on two or more labeled point sets
(with the same label set). We say that $G$ is compatible to the point sets if
the drawing of $G$ is plane for each of them (where each vertex of $G$ is
mapped to a unique label and thereby identified with a unique point of each
point set). Note that the labelings of the point sets can be predefined or
part of the solution. As an example, we mention the compatible triangulation
conjecture [4]: For any two sets $P_{1}$ and $P_{2}$ with the same number of
points and the same number of points on the boundary of the convex hull, there
is a labeling of the two sets such that there exists a triangulation which is
compatible to both sets, $P_{1}$ and $P_{2}$.

### Motivation and related work

The study of the type of compatibility considered in this work (the second
type from above) is motivated by applications in morphing [7, 17, 18], 2D
shape animation [12], or cartography [24].

Compatible triangulations were first introduced by Saalfeld [24] for labeled
point sets. He pointed out that for pairs of labeled point sets, compatible
triangulations do not always exist and studied the construction of compatible
triangulations using (possibly exponentially many) Steiner points. Aronov et
al. [9] and Babikov et al. [11] showed that $O(n^{2})$ Steiner points are
always sufficient, while Pach et al. [23] showed that $\Omega(n^{2})$ Steiner
points are sometimes necessary. Aronov et al. [9] also showed that for two
labeled polygons, the existence of a compatible triangulation without Steiner
points can be determined in polynomial time. The computational complexity
question for labeled point sets or polygons with holes is still open. For
polygons with holes, Lubiw and Mondal [22] showed NP-hardnes of deciding the
existence of a compatible triangulation with at most $k$ Steiner points.

The compatible triangulation conjecture states that – in contrast to labeled
point sets – two unlabeled point sets (in general position and with the same
number of extreme points) can always be compatibly triangulated without using
Steiner points. To date, the conjecture has only been proven for point sets
with at most three interior points [4]. Krasser [21] showed that more than two
point sets cannot always be compatibly triangulated. Danciger et al. [16]
considered compatibly triangulating two or more unlabeled point sets by using
few Steiner points.

Concerning compatible paths, Hui and Schaefer [19] showed that it is NP-hard
to decide whether two labeled point sets admit a compatible spanning path.
Arseneva et al. [10] presented efficient algorithms for finding a monotone
compatible spanning path, or a compatible spanning path inside simple polygons
(if they exist). Czyzowicz et al. [15] showed that any two convex labeled
point sets admit a compatible path of length at least $\sqrt{2n}$ and also
presented an $O(n^{2}\log n)$ algorithm to find such a path. In a similar
direction, results from Czabarka and Wang [14] imply a lower bound of
$(\sqrt{n-2}+2)/2$ on the length of the longest cycle compatible to two convex
point sets.

In this paper we will focus on compatible matchings. To the best of our
knowledge, previous results on (geometric) matchings study only compatibility
of the first type, that is, where two matchings are embedded on the same point
set. A well-studied question in this setting is whether any two perfect
matchings can be transformed into each other by a sequence of steps such that
at every step the intermediate graph is a perfect matching and the union of
any two consecutive matchings is plane. Aichholzer at al. [3] proved that such
a sequence of at most $O(\log n)$ steps always exists. Questions of whether
any matching of a given point set can be transformed into any other and how
many steps it takes (that is, the connectivity of and the distance in the so-
called reconfiguration graph of matchings, as well as its other properties)
have been investigated also for matchings on bicolored point sets and for
edge-disjoint compatible matchings, see for example [5, 8, 20].

(a)

(b)

Figure 1: (a) There is no perfect matching compatible to the two labeled sets.
(b) Any possible pair of matching edges crosses in exactly one of the three
sets.

### Our results

We study the second type of compatibility for matchings on two or more point
sets. This is a setting for which no previous comprehensive theory appears to
exist. Throughout this paper, we denote unlabeled point sets with $P$ and
labeled point sets with $\mathcal{P}$ (both mostly with added indices to
distinguish between different point sets).

We start by considering convex point sets: given two unlabeled convex point
sets $P_{1}$, $P_{2}$, both with $n$ points, we study the largest guaranteed
size $\operatorname{ccm}(n)$ of a compatible matching across all pairs of
labelings of $P_{1}$ and $P_{2}$. More formally, $\operatorname{ccm}(n)$ is
the minimum over all pairs of labelings of the maximum compatible matching
size for the accordingly labeled $n$-point set pairs. The largest compatible
matching for two labeled point sets is not necessarily perfect, see Fig. 1. In
Section 2, we present upper and lower bounds on $\operatorname{ccm}(n)$. In
particular, for any $n$ that is a multiple of 10, we construct two labeled
convex sets $\mathcal{P}_{1},\mathcal{P}_{2}$ of $n$ points each, for which
the largest compatible matching has $2n/5$ edges. Using probabilistic
arguments, we obtain an upper bound of
$\operatorname{ccm}(n)=\mathcal{O}(n^{2/3})$. For the lower bound, we show
that for any pair of labeled convex point sets $\mathcal{P}_{1}$,
$\mathcal{P}_{2}$ there exists a compatible matching consisting of
$\lfloor\sqrt{2n}\rfloor$ edges. This implies that
$\operatorname{ccm}(n)=\Omega(\sqrt{n})$.

We further extend our study to consider $\ell$ point sets in general position
instead of just two point sets in convex position. Given $\ell$ unlabeled sets
$P_{1},\dots,P_{\ell}$, each consisting of $n$ points in general position, we
denote by $\operatorname{cm}(n;P_{1},\dots,P_{\ell})$ the largest guaranteed
size of a compatible matching across all $\ell$-tuples of labelings of
$P_{1},\dots,P_{\ell}$. We remark that the size $n$ of the point sets is
included in the notation only for the sake of clarity (since our bounds depend
on $n$). In Section 3 we give bounds on
$\operatorname{cm}(n;P_{1},\dots,P_{\ell})$ for any sets
$P_{1},\dots,P_{\ell}$ of $n$ points in general position. Building on the
ideas of the proofs for two convex sets, we show that
$\operatorname{cm}(n;P_{1},\dots,P_{\ell})=\mathcal{O}(n^{2/(\ell+1)})$ and
that $\operatorname{cm}(n;P_{1},\dots,P_{\ell})=\Omega(n^{1/\ell})$.

Finally, we investigate the question of how many labeled copies of a given
unlabeled point set are needed so that the largest compatible matching
consists of a single edge. Already for four points in convex position, three
different sets are needed (and sufficient, see Fig. 1). In Section 4 we prove
that for any given set of $n\geq 5$ points in general position, $\Theta(\log
n)$ copies of it are necessary and sufficient for the existence of labelings
forcing that the largest compatible matching consists of a single edge.

For brevity, a plane matching that consists of $k$ edges is called a _$k$
-matching_.

##  2 Two convex sets

Throughout this section we consider two labeled convex point sets
$\mathcal{P}_{1}$, $\mathcal{P}_{2}$ consisting of $n$ points each. Without
loss of generality we assume that $\mathcal{P}_{1}$ is labeled $(1,2,\dots,n)$
in clockwise order and that $\mathcal{P}_{2}$ is labeled
$(\pi(1),\pi(2),\dots,\pi(n))$ in clockwise order for some permutation
$\pi\colon[n]\to[n]$. Note that for convex point sets, the compatible matching
question is a purely combinatorial one, in the sense that it only depends on
the two cyclic orders of $(1,2,\dots,n)$ given by the labelings rather than on
the concrete positions of the points. Using this fact, we determined
$\operatorname{ccm}(n)$ for small values of $n$ by computing the largest
compatible matching for each possible pair of labelings. The results of those
computations are listed in Table 1.

$n$ |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13 |  14 |  15 |  16
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\operatorname{ccm}(n)$ | 2 | 2 | 2 | 3 | 3 | 4 | 4 | 4 | 5 | 5 | 6 | 6 | 6
Table 1: The values of $\operatorname{ccm}(n)$ for $n=4,\dots,16$.

In the following, we present lower and upper bounds on the largest guaranteed
size $\operatorname{ccm}(n)$ of a compatible matching of any two such sets.
Starting with lower bounds, we present four pairwise incomparable results
(Theorem 2.1), each of them giving rise to a polynomial-time algorithm for
constructing a compatible $k$-matching with $k=\Omega(\sqrt{n})$ edges. The
results are ordered by the size of the obtained compatible $k$-matching, where
the last one gives the best lower bound for $\operatorname{ccm}(n)$, while the
three other results yield compatible matchings of special structure. The
second result can be generalized to any number of (not necessarily convex)
sets (Theorem 3.1). We remark that the results in [15] imply a lower bound of
$\sqrt{2n}/2$ for the size of the largest compatible matching, which is weaker
than the fourth result.

Before stating the theorem, we introduce the notion of a shape of a matching
on a convex point set which, informally stated, captures “how the matching
looks”. Consider a labeled point set $\mathcal{P}$ and a plane matching $M$ on
$\mathcal{P}$. Let $\mathcal{P}^{M}\subseteq\mathcal{P}$ be the points of
$\mathcal{P}$ that are incident to an edge of $M$. The _shape_ of $M$ is the
combinatorial embedding111The combinatorial embedding fixes the cyclic order
of incident edges for each vertex. of the union of $M$ and the boundary of the
convex hull of $\mathcal{P}^{M}$. Further, $M$ is called _non-nested_ if its
shape is a cycle, that is, all edges of $M$ lie on the boundary of the convex
hull of $\mathcal{P}^{M}$. Note that the shape of $M$ also determines the
number of its edges (even though some or all of the edges might be “hidden” in
the boundary of the convex hull of $\mathcal{P}^{M}$). We say that two
matchings have the _same shape_ , if their shapes are identical, possibly up
to a reflection.

######  Theorem 2.1 (Lower bound for two convex sets)

For any two labeled convex sets $\mathcal{P}_{1}$, $\mathcal{P}_{2}$ of $n$
points each, it holds that:

  1. (i)

If $n\geq(2k-2)^{2}+2$ then for any shape of a $k$-matching there exists a
compatible $k$-matching having that shape in both $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$.

  2. (ii)

If $n\geq k^{2}+2k-1$ then any maximal compatible matching consists of at
least $k$ edges.

  3. (iii)

If $n\geq k^{2}+k$ then there exists a compatible $k$-matching that is non-
nested in both $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$.

  4. (iv)

If $n\geq\frac{1}{2}k^{2}+k$ then there exists a compatible $k$-matching.

###### Proof

  1. (i)

By the circular Erdős-Szekeres Theorem [14], the permutation $\pi$ contains a
monotone subsequence $\sigma$ having length $2k$. The sequence
$S=\\{x_{i}|i\in\sigma\\}$ of points whose labels belong to $\sigma$ has the
same cyclic order in both sets $\mathcal{P}_{1}$, $\mathcal{P}_{2}$ (possibly
once clockwise and once counter-clockwise), hence any plane matching on $S$ in
$\mathcal{P}_{1}$ is also plane in $\mathcal{P}_{2}$ and has the same shape.

  2. (ii)

Suppose we have already found a compatible matching $M$ consisting of $m\leq
k-1$ edges. This leaves at least $n-2m\geq k^{2}+1$ points yet unmatched. The
unmatched points are split by the $m$ matching edges into at most $m+1\leq k$
subsets, both in $\mathcal{P}_{1}$ and in $\mathcal{P}_{2}$. Since there are
at most $k^{2}$ different ways to choose one such subset from
$\mathcal{P}_{1}$ and one from $\mathcal{P}_{2}$, there exist two yet
unmatched points $x$, $y$ that lie in the same subset in $\mathcal{P}_{1}$ and
in the same subset in $\mathcal{P}_{2}$. Hence $xy$ can be added to the
matching $M$.

  3. (iii)

This claim is equivalent to Problem 5 given at IMO 2017.222https://www.imo-
official.org/problems/IMO2017SL.pdf, Problem C4. For completeness we sketch a
proof (see Fig. 2): split the perimeter of $\mathcal{P}_{2}$ into $k$
contiguous blocks $B_{1},\dots,B_{k}$ consisting of $k+1$ points each (that
is, block $B_{1}$ consists of points labeled $\pi(1),\dots,\pi(k+1)$ and so
on). We aim to draw one matching edge per block. We process points $x_{i}$ in
order $i=1,\dots,n$ in which they appear in $\mathcal{P}_{1}$. Once some
block, say $B^{\star}$, contains two processed points, say $x_{u}$ and
$x_{v}$, we draw edge $x_{u}x_{v}$, discard other already processed points and
discard other points in $B^{\star}$. In this way, any time we draw an edge in
some block, we discard at most one point from each other block. Since each
block initially contains $k+1$ points, we will eventually draw one edge in
each block. The produced matching contains one edge per block, hence it is
non-nested in $\mathcal{P}_{2}$. Since points $x_{i}$ are processed in order
$i=1,\dots,n$, the matching is also non-nested in $\mathcal{P}_{1}$.

Figure 2: Theorem 2.1, Claim (iii): Illustration with $n=12$ points and $k=3$
blocks (grey). After drawing an edge we switch the color of processed points
(red to green to blue). Claim (iv): The permutation matrix $\Pi$ and two
$2$-balls (yellow). A 2-ball centered at $[5,7]$ would intersect a 2-ball at
$[7,9]$, so drawing the edge between points labeled 7, 9 forces us to discard
at most 2 other points (6 and 8).

  4. (iv)

The idea is to find two points $x_{i}$, $x_{j}$ that are close to each other
in the cyclic order in both $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$. The bound
is then established by drawing the edge $x_{i}x_{j}$, omitting all points on
the shorter arcs of $x_{i}x_{j}$ in both $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$, and proceeding recursively.

Consider the permutation matrix $\Pi$ given by $\pi$, that is, an $n\times n$
matrix such that $\Pi_{i,j}=1$ if $\pi(i)=j$ and 0 otherwise. Given an integer
$r>0$ and a cell $\Pi_{i,j}$ containing a digit 1, the _$r$ -ball_ centered at
$\Pi_{i,j}$ is a set $B(\Pi_{i,j},r)=\\{\Pi_{u,v}\;:\;|i-u|+|j-v|\leq r\\}$ of
cells whose $L_{1}$-distance from $\Pi_{i,j}$ is at most $r$, where all
indices are considered cyclically modulo $n$ (see Fig. 2). Note that an
$r$-ball contains $2r^{2}+2r+1$ cells.

Now suppose $n$ and $r$ satisfy $n\leq 2r^{2}+2r$ and consider $r$-balls
centered at all $n$ cells containing a digit 1. The balls in total cover
$n\cdot(2r^{2}+2r+1)>n^{2}$ cells, hence some two $r$-balls intersect and
their centers $\Pi_{i,\pi(i)}$, $\Pi_{j,\pi(j)}$ have $L_{1}$-distance at most
$2r$. This means that the shorter arcs between points labeled $\pi(i)$ and
$\pi(j)$ contain, together in both point sets $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$, at most $2r-2$ other points. Drawing an edge $\pi(i)\pi(j)$
and removing these $2r-2$ other points leaves convex sets in both
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ whose convex hulls do not intersect
the matched edge $\pi(i)\pi(j)$.

The rest is induction. The claim holds for $k\in\\{1,2\\}$. Suppose that
$k=2r$ is even and that $n=\frac{1}{2}k^{2}+k=2r^{2}+2r$. By the above
argument, find a “short” edge $x_{i}x_{j}$ and remove up to $2r-2$ other
points. This leaves $n-2r$ ($<2r^{2}+2r$) points, so find another edge
$x_{u}x_{v}$ and remove up to $2r-2$ other points. This leaves
$2r^{2}-2r=2(r-1)^{2}+2(r-1)$ points and the induction applies. Last, note
that the above shows that having $2r^{2}$ points implies a $(2r-1)$-matching.
Since $2r^{2}=\lceil\frac{1}{2}(2r-1)^{2}+2r-1\rceil$, the case of $k=2r-1$
odd and $n=\lceil\frac{1}{2}(2r-1)^{2}+2r-1\rceil$ is also settled. ∎

For the remainder of this section, we consider upper bounds on the size of
compatible matchings for pairs of convex point sets.

We first describe an explicit construction of two labeled point sets
$\mathcal{P}_{\operatorname{id}}$ and $\mathcal{P}_{\pi}$, where $n$ is a
multiple of 10, the set $\mathcal{P}_{\operatorname{id}}$ is labeled
$(1,2,\ldots,n)$ in clockwise order, and the set $\mathcal{P}_{\pi}$ is
labeled $(\pi(1),\pi(2),\ldots,\pi(n))$ in clockwise order, by defining a
specific permutation $\pi\colon[n]\to[n]$. We will show that any compatible
matching of $\mathcal{P}_{\operatorname{id}}$ and $\mathcal{P}_{\pi}$ misses
at least $n/5$ of the points.

Our building block for $\pi$ is the permutation $(2,4,1,5,3)$ of five
elements. For labeling the $n=5k$ points of $\mathcal{P}_{\pi}$ (with $k\geq
2$ even) we use the permutation $\pi=(2,4,1,5,3,\ 7,9,6,10,8,\
\dots,5(k\\!-\\!1)\\!+\\!2,5(k\\!-\\!1)\\!+\\!4,5(k\\!-\\!1)\\!+\\!1,5(k\\!-\\!1)\\!+\\!5,5(k\\!-\\!1)\\!+\\!3)$
that yields $k$ blocks of 5 points each in both $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$ (see Fig. 3).

Figure 3: The two labeled point sets $\mathcal{P}_{\operatorname{id}}$ and
$\mathcal{P}_{\pi}$ for the permutation $\pi$.

######  Proposition 1 (Constructive upper bound for two convex sets)

The largest compatible matching of the two labeled $n$-point sets
$\mathcal{P}_{\operatorname{id}}$ and $\mathcal{P}_{\pi}$ defined above
contains $\frac{2}{5}n$ edges.

###### Proof

Consider any compatible matching $M$ of $\mathcal{P}_{\operatorname{id}}$ and
$\mathcal{P}_{\pi}$. We show that any compatible matching misses at least one
point within each of the $k$ blocks. This gives $\frac{n}{5}$ unmatched points
and thus at most $\frac{2}{5}n$ edges in any compatible matching.

We classify the edges of any compatible matching $M$ into two types: those
that connect two points in one block (that is, edges with both labels in
$\\{i\\!+\\!1,\linebreak i\\!+\\!2,i\\!+\\!3,i\\!+\\!4,i\\!+\\!5\\}$ for some
$0\leq i\leq k-1$; we call them short edges) and all other edges, which
connect two points from different blocks (we call them _long_ edges). To show
that $M$ misses at least one point of each block $B$, we distinguish two
cases:

Case 1:

_$B$ contains at least one short edge._

We show that there is always at least one unmatched point in $B$. W.l.o.g.,
let $B$ be the block with labels $1,\ldots,5$. For each of the possible
$\binom{5}{2}=10$ short edges, we will verify that if we include it, then we
inevitably obtain a point of $B$ that can not be matched in either
$\mathcal{P}_{1}$ or $\mathcal{P}_{2}$ (see Fig. 3). We argue by
contradiction: suppose $M$ matches all points of $B$ and $B$ contains a short
edge. First, if a short edge cuts off an odd number of points in $B$ in either
$\mathcal{P}_{1}$ or $\mathcal{P}_{2}$, then one of these points is unmatched.
This is the case for the edges $(1,3),(1,5),(2,4)$ and $(3,5)$ in
$\mathcal{P}_{1}$ and for the edges $(1,2),(2,3)$ and $(4,5)$ in
$\mathcal{P}_{2}$. So none of these edges can be a short edge in $B$ such that
all points of $B$ are matched. Second, if $B$ contains the edge $(1,4)$, then
the edge $(2,3)$ has to be in $M$ due to $\mathcal{P}_{1}$ and is therefore
also a short edge in $B$. This is a contradiction since the edge $(2,3)$
cannot be a short edge in $B$. Third, if $B$ contains the edge $(2,5)$, then
the edge $(3,4)$ has to be in $M$ due to $\mathcal{P}_{1}$. This is a
contradiction since the edges $(2,5)$ and $(3,4)$ are not compatible due to
$\mathcal{P}_{2}$. And finally, if $B$ contains the edge $(3,4)$, then the
edge $(1,5)$ has to be in $M$ due to $\mathcal{P}_{2}$ and is therefore also a
short edge in $B$. This is a contradiction since the edge $(1,5)$ cannot be a
short edge in $B$. This completes the proof that if $B$ contains a short edge,
then $M$ does not match all points of $B$.

Case 2:

_All five points in $B$ are matched by a long edge._

We argue that, under the assumption that all five points in $B$ are matched
(by a long edge), all those five edges in fact must go to the same block
$B^{\prime}$, which we then show to be impossible. Consider a pair of numbers
$a$, $b$ that lie in the same block whose relative position within that block
is different in $\mathcal{P}_{1}$ and in $\mathcal{P}_{2}$ (for example, 1 and
2 but not 1 and 3). Suppose $b$ is matched to $b^{\prime}$. Then $a$ has to be
matched to a point on the same side of the line $bb^{\prime}$ as $a$, in both
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$. This is impossible unless $a$ is
matched to a point in the same block as $b^{\prime}$ that moreover happens to
lie on the correct side of $b^{\prime}$ in both $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$. Hence for any such pair $a$, $b$, the points $a$ and $b$
are matched to the same block. It remains to notice that
$(2,1),(1,4),(4,3),(3,5)$ are all eligible $(a,b)$ pairs, hence all five edges
go to the same block $B^{\prime}$. However, there is only one non-crossing
perfect matching of $B$ and $B^{\prime}$ in $\mathcal{P}_{1}$ and we easily
check that it is not compatible with $\mathcal{P}_{2}$.

To see that the bound is tight, note that within each block of
$\mathcal{P}_{\pi}$ we can match the first two points and the next two points.
This yields a compatible matching of $\mathcal{P}_{\operatorname{id}}$ and
$\mathcal{P}_{\pi}$ with $2k=\frac{2}{5}n$ edges consisting only of short
edges. ∎

The above construction yields an upper bound of
$\operatorname{ccm}(n)\leq\lceil\frac{2}{5}n\rceil$. However, this bound is
not tight. We next show in a probabilistic way that there exists a permutation
$\pi\colon[n]\to[n]$ for which the largest compatible matching consists of
$k=\mathcal{O}(n^{2/3})$ edges. In Section 3, we will extend this approach to
any number of point sets, not necessarily in convex position (Theorem 3.2).

######  Theorem 2.2 (Probabilistic upper bound for two convex sets)

Fix $n$ and let $k=4n^{2/3}$. Then two convex sets $P_{1}$, $P_{2}$ of $n$
points each can be labeled such that the largest compatible matching consists
of fewer than $k$ edges.

###### Proof

Let $\mathcal{P}_{1}$ be $P_{1}$ with labeling $(1,2,\dots,n)$ in clockwise
order and let $P_{2}$ not yet be labeled. The idea for this proof is that for
large $n$ there are more ways to label $P_{2}$ than there are ways to draw a
compatible $k$-matching.

For any $k\leq n$, let $f(k)$ be the number of plane $k$-matchings of $P_{i}$,
$i\in\\{1,2\\}$ (that is, matchings leaving $n-2k$ points unmatched). As there
are $\binom{n}{2k}$ ways to select the $2k$ points to be matched and the
number of plane perfect matching on those points is
$\frac{1}{k+1}\binom{2k}{k}$ (the $k$-th Catalan number), we obtain

$f(k)=\binom{n}{2k}\cdot\frac{1}{k+1}\binom{2k}{k}\leq\frac{n!}{(n-2k)!\cdot
k!\cdot k!}\ .$

Given two plane $k$-matchings, one of $\mathcal{P}_{1}$ and one of $P_{2}$,
there are exactly $g(k)=(n-2k)!\cdot k!\cdot 2^{k}$ labelings of $P_{2}$ for
which those two matchings constitute a compatible $k$-matching: there are
$(n-2k)!$ ways to label the unmatched points of $P_{2}$, $k!$ ways to pair up
the matching edges and $2^{k}$ ways to label their endpoints.

Therefore, $(f(k))^{2}g(k)$ is an upper bound for the number of labelings
$\pi$ of $P_{2}$ such that there is a compatible $k$-matching for
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ ($P_{2}$ with labeling $\pi$). On the
other hand, there are $n!$ labelings of $P_{2}$ in total.

Our goal is to show that $(f(k))^{2}\cdot g(k)<n!$. If we succeed, then there
exists a labeling $\pi$ of $P_{2}$ such that there is no compatible
$k$-matching for $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ ($P_{2}$ with
labeling $\pi$). Canceling some of the factorials and using standard bounds
$(n/{\operatorname{e}})^{n}<n!<n^{n}$ on the remaining ones (where
${\operatorname{e}}$ denotes Euler’s number), we obtain

$\displaystyle\frac{(f(k))^{2}\cdot g(k)}{n!}\leq\frac{n!\cdot
2^{k}}{(n-2k)!\cdot(k!)^{3}}\leq\frac{n^{2k}\cdot
2^{k}}{(k/{\operatorname{e}})^{3k}}$ $\displaystyle=$
$\displaystyle\left(\frac{2{\operatorname{e}}^{3}n^{2}}{k^{3}}\right)^{k}.$

For $k\geq 4n^{2/3}$, the above expression is less than one (we have
$2{\operatorname{e}}^{3}<4^{3}$), which completes the proof. ∎

##  3 Generalized and Multiple Sets

In this section we generalize our results in two ways, by considering point
sets in general position and more than two sets. We again start with lower
bounds. Theorem 3.1, which is a generalization of the second result of Theorem
2.1, implies that for any $\ell$-tuple of point sets $P_{1},\dots,P_{\ell}$ we
have $\operatorname{cm}(n;P_{1},\dots,P_{\ell})=\Omega(n^{1/\ell})$.

######  Theorem 3.1 (Lower bound for multiple sets)

Let $\mathcal{P}_{1},\mathcal{P}_{2},\dots,\mathcal{P}_{\ell}$ be labeled sets
of $n$ points each. If $n\geq k^{\ell}+2k-1$, then any maximal compatible
matching consists of at least $k$ edges.

###### Proof

We extend the idea from the proof of Theorem 2.1, part (ii): suppose we have
already found a compatible matching $M$ consisting of $m\leq k-1$ edges. This
leaves at least $k^{\ell}+2k-1-m\geq k^{\ell}+2k-1-2(k-1)=k^{\ell}+1$ points
yet unmatched. Imagine the $\ell$ point sets live in $\ell$ different planes.
We process the $m$ matching edges one by one. When an edge is processed, we
extend it along its line in both directions until it hits another matching
edge or an extension of a previously processed edge (in all $\ell$ planes). In
this way, the $m$ lines partition each plane into $m+1\leq k$ convex regions.
By simple counting ($k^{\ell}+1>k^{\ell}$), there exist two yet unmatched
points $x$, $y$ that lie in the same region in each of the $\ell$ planes.
Hence $xy$ can be added to the matching $M$. ∎

Regarding upper bounds, the following theorem implies that for any fixed
$\ell$ and any $\ell$-tuple of point sets $P_{1},\dots,P_{\ell}$, we have
$\operatorname{cm}(n;P_{1},\dots,P_{\ell})=\mathcal{O}(n^{2/(\ell+1)})$.

######  Theorem 3.2 (Probabilistic upper bound for multiple sets)

Fix $n$ and $\ell$ and let $k=125\cdot n^{2/(\ell+1)}$. Then any $\ell$ sets
$P_{1},\dots,P_{\ell}$ of $n$ points each, where each $P_{i}$ is in general
position, can be labeled such that the largest compatible matching consists of
fewer than $k$ edges.

This theorem can be proven by extending the idea from the proof of Theorem 2.2
and combining results of Sharir, Sheffer and Welzl [26] and Sharir and Sheffer
[25] on the number of triangulations and plane perfect matchings.

###### Proof

Let $\mathcal{P}_{1}$ be $P_{1}$ with labeling $(1,2,\dots,n)$ in clockwise
order and suppose that the remaining $\ell-1$ sets are not yet labeled. Let
$k\leq n$ and let $f_{i}(k)$, $1\leq i\leq\ell$, be the number of
$k$-matchings of $P_{i}$. Sharir, Sheffer and Welzl showed in [26] that the
number of plane perfect matchings of any set $P$ of $k$ points in general
position is at most $8\cdot(3/2)^{(k/4)}\cdot tr(P)$, where $tr(P)$ denotes
the number of triangulations of $P$. Sharir and Sheffer also showed in [25]
that the number of triangulations of $P$ is at most $30^{k}$. This implies
that there are also at most $8\cdot 33.21^{k}$ different perfect matchings of
$P$. By counting this upper bound for every possible $k$-point subset of
$P_{i}$, we obtain

$\displaystyle f_{i}(k)\leq$ $\displaystyle\binom{n}{2k}\cdot 8\cdot
33.21^{k}.$

Next, consider an $\ell$-tuple $(M_{1},\dots,M_{\ell})$ of matchings on
$P_{1},\dots,P_{\ell}$, respectively, consisting of $k$ edges each. Notice
that any such $\ell$-tuple forms a compatible matching for

$\displaystyle g(k)$ $\displaystyle=$ $\displaystyle\left((n-2k)!\cdot k!\cdot
2^{k}\right)^{\ell-1}$

combinations of labelings for $P_{2},\dots,P_{\ell}$. On the other hand, there
are $(n!)^{\ell-1}$ such combinations of labelings for $P_{2},\ldots,P_{\ell}$
in total. It suffices to show that

$\displaystyle\left(\prod_{i=1}^{\ell}f_{i}(k)\right)\cdot g(k)$
$\displaystyle<$ $\displaystyle(n!)^{\ell-1}$

for guaranteeing the existence of a combination of labelings for
$P_{2},\ldots,P_{\ell}$ such that there is no compatible $k$-matching for the
resulting labeled sets $\mathcal{P}_{1},\ldots,\mathcal{P}_{\ell}$. As before,
we expand the binomials into factorials, cancel some of them and use standard
bounds $(n/e)^{n}<n!<n^{n}$ on the remaining ones (where $e$ again denotes
Euler’s number) to obtain

$\displaystyle\frac{\left(\prod_{i=1}^{\ell}f_{i}(k)\right)\cdot
g(k)}{(n!)^{\ell-1}}$ $\displaystyle=$
$\displaystyle\frac{n!\cdot(8\cdot{33.21}^{k})^{\ell}(k!)^{\ell-1}(2^{k})^{\ell-1}}{(n-2k)!((2k)!)^{\ell}}$
$\displaystyle\leq$ $\displaystyle
8^{{\ell}}\frac{n^{2k}\cdot(66.42^{\ell})^{k}(k^{\ell-1})^{k}(e^{2\ell})^{k}}{((2k)^{\ell})^{2k}}\leq
8^{{\ell}}\left[(16.605\cdot
e^{2})^{\ell}\cdot\frac{n^{2}}{k^{\ell+1}}\right]^{k}.$

When $k=125\cdot n^{2/({\ell}+1)}$, then also $k\geq 125$ holds. Further, the
expression inside the brackets is less than $\frac{1}{1.018^{\ell}}$ (we have
$16.605\cdot e^{2}<\frac{125}{1.018}$). Since $8<1.018^{125}\leq 1.018^{k}$,
this completes the proof. ∎

We remark that the upper bound of $33.21^{k}$ for the number of plane perfect
matchings of any set of $k$ points in the plane in general position is by far
not tight. Actually, Sharir and Welzl [27] showed that this number can be
bounded by $O(10.05^{k})$. However, for the above proof, we require an
explicit upper bound that holds for any value of $k\geq 125$ and hence we did
not use this result.

##  4 Forcing a single-edge compatible matching

In this section we consider the following question: Given an unlabeled point
set $P$ with $n$ points, is there an integer $\ell$ such that there exist
$\ell$ labelings of $P$ for which every compatible matching has at most one
edge? If $\ell$ exists, we denote as $\operatorname{force}(n;P)$ the minimum
number $\ell$ of copies of $P$ such that $\operatorname{cm}(n;P,\dots,P)=1$
(where $P$ appears $\operatorname{force}(n;P)$ times). Otherwise, we set
$\operatorname{force}(n;P)=\infty$. In other words, we are asking for the
existence (and minimal number) of labelings of the set $P$ so that any pair of
labeled edges crosses for at least one labeling. We remark that, again, the
size $n$ of the point sets is included in the notation only for the sake of
clarity.

Note that $\operatorname{force}(n;P)=\infty$ if and only if the straight-line
drawing of $K_{n}$ on $P$ does not contain any crossing. Hence
$\operatorname{force}(n;P)$ is finite for any set $P$ of $n\geq 5$ points.
More specifically, if the straight-line drawing of $K_{n}$ on $P$ contains at
least one crossing, then $\operatorname{force}(n;P)$ is at most $3{n\choose
4}=\mathcal{O}(n^{4})$. This bound is due to the fact that, if we focus on one
crossing edge pair, then there are $3{n\choose 4}$ possible labelings for
these two edges. If the straight-line drawing of $K_{n}$ on $P$ contains
exactly one crossing, then $3{n\choose 4}$ is tight: In this case, each pair
of labeled edges must be mapped to the unique crossing edge pair, as
otherwise, that pair of labeled edges would be compatible. Hence, any point
set $P_{4}$ of 4 points in convex position has
$\operatorname{force}(4;P_{4})=3$ and any point set $P_{5}$ of 5 points with
triangular convex hull has $\operatorname{force}(5;R_{5})=15$.

We first focus on upper bounds and on the case when $P$ is in convex position.
We denote by $\operatorname{cforce}(n)$ the minimum number of copies of a
convex set with $n$ points that need to be labeled so that the largest
compatible matching consists of only a single edge.

Let $b(n)=\lceil\log_{2}n\rceil$, which is the number of bits that are needed
to represent the labels 1 to $n$. We construct a family of
$\frac{3}{2}b(n)^{2}$ labeled convex $n$-point sets such that all pairs of
edges cross in at least one set. First consider three labeled convex point
sets, which are obtained by partitioning the set of labels into four blocks
$A$, $B$, $C$, $D$, and combining those blocks in different orders and
orientations as depicted in Fig. 4. The order within a block is arbitrary, but
identical for all three sets (up to reflection; those block orientations are
indicated by arrows).

(a)

(b)

(c)

Figure 4: Three labeled point sets obtained from different orders and
orientations of four blocks $A$, $B$, $C$, and $D$.

######  Lemma 1 ()

Consider three convex point sets $\mathcal{P}_{1}$, $\mathcal{P}_{2}$, and
$\mathcal{P}_{3}$ that are labeled as in Fig. 4 for some partition $A$, $B$,
$C$, and $D$ of their label set. Then any pair of independent333Two edges are
independent if they do not share an endpoint. edges, where none of them has
both labels in one of the blocks $A$, $B$, $C$, and $D$, forms a crossing in
at least one of $\mathcal{P}_{1}$, $\mathcal{P}_{2}$, and $\mathcal{P}_{3}$.

###### Proof

We consider three cases, depending on the number $x$ of blocks containing
endpoints of the edges $e$ and $f$.

Case $x=2$:

Then $e$ and $f$ are spanned by the same two subsets. As any pair of blocks
shows up in the same and in inverse orientation in at least one of the three
drawings, this guarantees a crossing. For example, let the two subsets be $A$
and $B$. They have the same orientation in Fig. 4(a) and 4(b), but inverse
orientation in Fig. 4(c). An analogous property holds for the remaining five
combinations.

Case $x=3$:

W.l.o.g. $e$ and $f$ have their starting point in the same subset, but the
endpoints in different subsets. There are 12 possible configurations of one
common and two disjoint subsets, and it is straightforward to check that each
situation shows up in both possible orientations with respect to the common
set. For example, let the common set be $A$, and the other sets $C$ and $D$.
The orientation of $A$ is the same in all three drawings, but the order of $C$
and $D$ is inverted in Fig. 4(a) and 4(c). If the common set is $B$ and the
two other sets are again $C$ and $D$, then order of the three sets is the same
in all three drawings, but the orientation of the common set $B$ is inverted
in Fig. 4(a) and 4(c). Thus, in both cases a crossing is guaranteed.

Case $x=4$:

In this case the orientation of the subsets is not relevant. There are only
three possible combinations of such edges ($A-B$ with $C-D$, $A-C$ with $B-D$,
and $A-D$ with $B-C$) and the three drawings cover one case each. ∎

We next identify a small number of 4-partitions of the label set
$\\{1,2,\ldots,n\\}$ such that each edge pair fulfills the condition of Lemma
1 in at least one of the partitions (when the four subsets form blocks). This
yields the following constructive upper bound for $\operatorname{cforce}(n)$.

######  Proposition 2 (Constructive upper bound on $\operatorname{cforce}(n)$)

For any $n\\!\geq\\!4$ and for $b(n)=\lceil\log_{2}n\rceil$, we can define
$3{b(n)\choose 2}$ labeled convex sets of $n$ points such that the largest
matching compatible to all of them consists of a single edge.

###### Proof

Given a convex set of $n$ points, we construct $b(n)\choose 2$ 4-partitions of
the labels and use each such partition to obtain three labeled point sets as
depicted in Fig. 4. For any two bit positions $i,j$, $0\leq i\neq j<b(n)$, of
the labels, partition the label set $\\{1,2,\ldots,n\\}$ so that $A$ contains
all labels where those two bits are zero, $B$ those where the bits are zero-
one, $C$ those with one-zero, and finally $D$ the ones with both one. This
gives $b(n)\choose 2$ different partitions.

Now consider two arbitrary edges $e$ and $f$. Then there is a bit position in
which the two endpoints of $e$ have different values, and the same is true for
$f$. Let $i$ and $j$, respectively, be those positions. If this would give
$i=j$, then choose $j$ arbitrarily but not equal to $i$. By Lemma 1, the edges
$e$ and $f$ cross in one of the three labeled point sets for the partition
generated for $i$ and $j$. ∎

The upper bound $\mathcal{O}(\log^{2}n)$ of $\operatorname{cforce}(n)$ from
Proposition 2 is constructive but it is not asymptotically tight. Next we
present a probabilistic argument which shows that we actually have
$\operatorname{force}(n;P)=\mathcal{O}(\log n)$ for any point set $P$ of
$n\geq 5$ points.

######  Lemma 2 (Probabilistic upper bound on $\operatorname{force}(n;P)$)

Given a set ${P}$ of $n\geq 5$ points in general position, there exists a
constant $c_{P}\geq 15/14$ such that
$\operatorname{force}(n;P)\leq\log_{c_{P}}(3{n\choose 4})=\mathcal{O}(\log
n)$.

###### Proof

Fix $P$ and let $\alpha_{P}\in(0,1)$ be the proportion of 4-tuples of points
in ${P}$ that are in convex position. Note that since any 5-tuple of points
contains at least one 4-tuple in convex position, we have $\alpha_{P}\geq 1/5$
(here we use $n\geq 5$).

There are $r=3\binom{n}{4}$ pairs of non-incident edges. Fix one of them, say
$ac$ and $bd$. Note that when ${P}$ is labeled uniformly at random, the edges
$ac$, $bd$ intersect with constant probability $\alpha_{P}/3$: indeed, the
edges intersect if their 4 endpoints form a convex quadrilateral and the
points $a$, $b$, $c$, $d$ lie on its perimeter in two out of the six possible
cyclic orders.

Now set $c_{P}=(1-\alpha_{P}/3)^{-1}\geq 15/14$ and consider
$\ell>\log_{c_{P}}(r)$ copies of ${P}$ labeled independently and uniformly at
random. A pair of edges without common vertex is compatible (with respect to
the $\ell$ labeled point sets) if it is non-crossing in all $\ell$ point sets.
As the labelings are chosen independently and uniformly at random, any fixed
pair of edges is compatible with probability
$\rho=(1-\alpha_{P}/3)^{\ell}<1/r$. By linearity of expectation, the expected
number of compatible pairs of edges is $r\cdot\rho<1$. Therefore there exists
a labeling of the $\ell$ point sets for which no pair of edges is compatible.
In such a labeling, the largest compatible matching consists of a single edge.
∎

We remark that for a fixed set $P$, one can often obtain a better lower bound
on the parameter $\alpha_{P}$ used in the proof and thus a better lower bound
on $c_{P}$, which then gives a constant factor improvement on
$\operatorname{force}(n;P)$. Specifically, finding the constant
$\alpha:=\lim_{n\to\infty}\inf_{P,|P|\geq n}\\{\alpha_{P}\\}$ is a topic of
high relevance in connection with the rectilinear crossing number of the
complete graph, see [2] for a nice survey of this area. The currently best
known bounds are $0.37997256<\alpha<0.38044919$ [1, 6]. Moreover, when $P$ is
in convex position we have $\alpha_{P}=1$ and thus the above proof implies
$\operatorname{cforce}(n)\leq\log_{3/2}(3{n\choose 4})$. On the other hand,
none of these observations leads to an asymptotic improvement on the upper
bound of $\operatorname{force}(n;P)$ or $\operatorname{cforce}(n)$. In the
following we show that any such asymptotic improvement is in fact impossible.

######  Lemma 3 (Lower bound on $\operatorname{force}(n;P)$)

Fix $k\geq 1$ and let $P$ be any set of $n=2^{k}+3$ points in general
position. Then $\operatorname{force}(n;P)\geq k+2=\Omega(\log n)$.

###### Proof

We use a similar argument as the one used in Theorem 3.1. Denote by
$\mathcal{P}_{1},\dots,\mathcal{P}_{k+1}$ any $k+1$ labeled copies of $P$.
Take an arbitrary edge $ab$ on the convex hull of $\mathcal{P}_{k+1}$. The
line containing $ab$ divides each of $\mathcal{P}_{1},\dots,\mathcal{P}_{k}$
into two parts (one possibly empty). Since there are $n-2=2^{k}+1>2^{k}$
unmatched points, there exist two points, say $x$, $y$, that lie in the same
part, for each $i=1,\dots,k$. Thus the two edges $xy$ and $ab$ form a
compatible 2-matching implying that $\operatorname{force}(n;P)\geq k+2$. ∎

Combining upper and lower bounds for $\operatorname{force}(n;P)$ from Lemmata
3 and 2, we obtain the following conclusion:

###### Theorem 4.1

For every set $P$ of $n\geq 5$ points in general position, it holds that

$\displaystyle\operatorname{force}(n;P)$ $\displaystyle=$
$\displaystyle\Theta(\log n).$

##  5 Conclusion and open problems

In this work we studied the size of compatible matchings. A natural open
problem is the computational complexity of finding compatible matchings of a
certain size or even deciding their existence: How fast can we decide if two
(or more) given (general or convex) labeled point sets have a perfect
compatible matching (or a compatible matching of size $k$)?

We showed that for any $\ell$ labeled $n$-point sets, there is always a
compatible matching of size $\Omega(n^{1/\ell})$. On the other hand, for any
$\ell$ unlabeled $n$-point sets, there exist labelings of these $\ell$ point
sets such that the largest compatible matching has size
$\mathcal{O}(n^{2/(\ell+1)})$. Even for only two sets these bounds are
currently the best ones known. It would be interesting to close this gap, even
if this only hold for a special point set.

Furthermore, for two convex point sets, we only have an explicit labeling such
that the largest compatible matching has $2n/5$ matching edges. This leads to
the following open problems: Can we give a family of explicit labeled convex
point sets, such that the largest compatible matching has size
$\mathcal{O}(n^{1-\epsilon})$? Furthermore, can we give a labeling of $\ell$
point sets that allows only small compatible matchings? Note that the second
problem is also open if we only look at convex point sets. It would also be
nice to have a construction that matches the probabilistic bound, even if the
construction only works for special point sets.

Further we studied how many labeled copies of a point set needed such that any
compatible matching only contains one edge. We showed that $\Theta(\log n)$
point sets are sufficient and that this bound is tight. We constructed a
labeling of roughly $\frac{3}{2}\log^{2}n$ convex labeled point sets that
obtain this property. This leads to the following question: Can we construct a
family of $\Theta(\log n)$ (maybe convex) labeled point sets such that any
compatible matching only contains one edge?

Finally, as a game version of this problem, consider the following game: Two
players alternately add an edge which must neither cross nor be incident to
any previously added edge. The last player who is able to add such an edge
wins. It is not hard to see that for a single set of points in convex
position, this is the well-known game Dawson’s Kayles, see e.g. [13]. This
game can be perfectly solved using the nimber theory developed by Sprague-
Grundy, see also [13] for a nice introduction to the area. An interesting
generalization of Dawson’s Kayles occurs when the players use two (or more)
labeled (convex) point sets and add compatible edges.

## References

  * [1] Ábrego, B.M., Fernández-Merchant, S., Leaños, J., Salazar, G.: A central approach to bound the number of crossings in a generalized configuration. In: Proceedings of the 4th Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS’07). vol. 30, pp. 273–278 (2008). https://doi.org/10.1016/j.endm.2008.01.047
  * [2] Ábrego, B.M., Fernández-Merchant, S., Salazar, G.: The rectilinear crossing number of ${K}_{n}$: closing in (or are we?). In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 5–18. Springer (2013). https://doi.org/10.1007/978-1-4614-0110-0_2
  * [3] Aichholzer, O., Bereg, S., Dumitrescu, A., García, A., Huemer, C., Hurtado, F., Kano, M., Márquez, A., Rappaport, D., Smorodinsky, S., Souvaine, D., Urrutia, J., Wood, D.: Compatible geometric matchings. Computational Geometry: Theory and Applications 42(6–7), 617–626 (2009). https://doi.org/10.1016/j.comgeo.2008.12.005
  * [4] Aichholzer, O., Aurenhammer, F., Hurtado, F., Krasser, H.: Towards compatible triangulations. Theoretical Computer Science 296(1), 3–13 (2003). https://doi.org/10.1016/S0304-3975(02)00428-0
  * [5] Aichholzer, O., Barba, L., Hackl, T., Pilz, A., Vogtenhuber, B.: Linear transformation distance for bichromatic matchings. Computational Geometry: Theory and Application 68, 77–88 (2018)
  * [6] Aichholzer, O., Duque, F., Fabila-Monroy, R., Hidalgo-Toscano, C., García-Quintero, O.E.: An ongoing project to improve the rectilinear and the pseudolinear crossing constants. ArXiv e-Prints (2020)
  * [7] Alamdari, S., Angelini, P., Barrera-Cruz, F., Chan, T., Da Lozzo, G., Battista, G., Frati, F., Haxell, P., Lubiw, A., Patrignani, M., Roselli, V., Singla, S., Wilkinson, B.: How to morph planar graph drawings. SIAM Journal on Computing 46(2), 824–852 (2017). https://doi.org/10.1137/16M1069171
  * [8] Aloupis, G., Barba, L., Langerman, S., Souvaine, D.: Bichromatic compatible matchings. Computational Geometry: Theory and Applications 48(8), 622–633 (2015). https://doi.org/10.1016/j.comgeo.2014.08.009
  * [9] Aronov, B., Seidel, R., Souvaine, D.: On compatible triangulations of simple polygons. Computational Geometry: Theory and Applications 3, 27–35 (1993). https://doi.org/10.1016/0925-7721(93)90028-5
  * [10] Arseneva, E., Bahoo, Y., Biniaz, A., Cano, P., Chanchary, F., Iacono, J., Jain, K., Lubiw, A., Mondal, D., Sheikhan, K., Tóth, C.D.: Compatible paths on labelled point sets. In: Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG). pp. 54–60 (2018)
  * [11] Babikov, M., Souvaine, D.L., Wenger, R.: Constructing piecewise linear homeomorphisms of polygons with holes. In: Proceedings of the 9th Canadian Conference on Computational Geometry (CCCG) (1997)
  * [12] Baxter III, W.V., Barla, P., Anjyo, K.: Compatible embedding for 2d shape animation. IEEE Transactions on Visualization and Computer Graphics 15(5), 867–879 (2009)
  * [13] Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning ways for your mathematical plays, vol. 1. A. K. Peters Ltd., second edn. (2001)
  * [14] Czabarka, É., Wang, Z.: Erdős–Szekeres theorem for cyclic permutations. Involve, a Journal of Mathematics 12(2), 351–360 (2019). https://doi.org/10.2140/involve.2019.12.351
  * [15] Czyzowicz, J., Kranakis, E., Krizanc, D., Urrutia, J.: Maximal length common non-intersecting paths. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG’96). pp. 185–189 (1996)
  * [16] Danciger, J., Devadoss, S.L., Sheehy, D.: Compatible triangulations and point partitions by series-triangular graphs. Computational Geometry: Theory and Applications 34(3), 195–202 (2006). https://doi.org/10.1016/j.comgeo.2005.11.003
  * [17] Erten, C., Kobourov, S.G., Pitta, C.: Intersection-free morphing of planar graphs. In: Liotta, G. (ed.) Proceedings of the 11th International Symposium on Graph Drawing (GD’03). pp. 320–331. LNCS, Springer (2004). https://doi.org/10.1007/978-3-540-24595-7_30
  * [18] Floater, M.S., Gotsman, C.: How to morph tilings injectively. Journal of Computational and Applied Mathematics 101, 117–129 (1999). https://doi.org/10.1016/S0377-0427(98)00202-7
  * [19] Hui, P., Schaefer, M.: Paired pointset traversal. In: Fleischer, R., Trippen, G. (eds.) Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC). LNCS, vol. 3341, pp. 534–544. Springer (2004). https://doi.org/10.1007/b104582
  * [20] Ishaque, M., Souvaine, D.L., Tóth, C.D.: Disjoint compatible geometric matchings. Discrete & Computational Geometry 49, 89–131 (2013). https://doi.org/10.1007/s00454-012-9466-9
  * [21] Krasser, H.: Kompatible Triangulierungen ebener Punktmengen. Master’s thesis, Graz University of Technology (1999)
  * [22] Lubiw, A., Mondal, D.: On compatible triangulations with a minimum number of steiner points. Theoretical Computer Science 835, 97–107 (2020). https://doi.org/https://doi.org/10.1016/j.tcs.2020.06.014, http://www.sciencedirect.com/science/article/pii/S0304397520303546
  * [23] Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica 16(1), 111–117 (1996)
  * [24] Saalfeld, A.: Joint triangulations and triangulation maps. In: Proceedings of the 3rd Annual Symposium on Computational Geometry (SCG’87). pp. 195–204 (1987). https://doi.org/10.1145/41958.41979
  * [25] Sharir, M., Sheffer, A.: Counting triangulations of planar point sets. Electronic Journal of Combinatorics 18(1) (2011). https://doi.org/10.37236/557
  * [26] Sharir, M., Sheffer, A., Welzl, E.: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique. Journal of Combinatorial Theory, Series A 120(4), 777–794 (2013). https://doi.org/10.1016/j.jcta.2013.01.002
  * [27] Sharir, M., Welzl, E.: On the number of crossing-free matchings, cycles, and partitions. SIAM Journal on Computing 36(3), 695–720 (2006). https://doi.org/10.1137/050636036