# Focusing Airborne Ultrasound with Partially Occluded Emission from
Rectangular Plate with Flexural Vibration Mode

Keisuke Hasegawa*, Masaya Fujimori*, and Masaya Takasaki

## Abstract

We propose a focusing method of intense midair ultrasound out of ultrasonic
emission from a single flexurally vibrating square plate partially covered
with a purposely designed amplitude mask. Many applications relying on
nonlinear acoustic effects, such as radiation force employed in acoustic
levitation, have been devised. For those applications, focused intense
airborne ultrasound is conventionally formed using phased arrays of
transducers or sound sources with specific fabricated shapes. However, the
former strategies are considerably costly, and the latter may require minute
three-dimensional fabrication processes, which both hinder their utility,
especially for the construction of a large ultrasound emitting aperture. Our
method offers a possible solution for this, where the amplitude masks are
designed in a fashion similar to the Freznel-zone-plate designing, but
according to the positions of nodes and antinodes of the vibrating plate that
are measured beforehand.

We experimentally demonstrate the successful formation of midair ultrasound
focus at a desired position. Our method only requires a monolithic plate, a
driving transducer under the plate, and an amplitude mask fabricated out of
laser machining processes of an acrylic plate. Magnification of the spatial
scale of ultrasound apertures based on our method is much more readily and
affordably achieved than conventional methods, which will lead to new midair
ultrasound applications with the whole room workspace. 111K. H and M. F
equally contributed to this paper.
K. H. and M. T, Authors are and with Department of Mechanical Science,
Graduate School of Science and Engineering, Saitama University, 338-8570,
Saitama, Japan.
M. F. was with the Department of Mechanical Engineering and System Design,
Faculty of Engineering, Saitama University. K. H. Author is to whom
corresponding should be addressed (e-mail: keisuke@mech.saitama-u.ac.jp).
This project is financially supported by Japan Society for the Promotion of
Science (JSPS), Grant No. 23K18488, Japan.

##  1 Introduction

###  1.1 Prevalent use of focused midair ultrasound and current focusing
methods

Applications of midair focusing ultrasound have been continuously
investigated, especially regarding the ones that rely on nonlinear acoustic
effects exhibited by intense ultrasound fields, such as acoustic radiation
force [1, 2], acoustic streaming [3, 4, 5], and parametric array [6, 7]. The
unique nature of focused intense midair ultrasound that it can engender non-
contact mechanical effects at an arbitrary pinpoint position in the air has
materialized many practical applications such as acoustic levitation [8, 9,
10], midair object manipulation [11, 12], non-contact tactile displays [13,
14, 15], midair fragrance transportation [16], remote suppression of short-
range exposure to infectious aerosols [17], and so forth. On the other hand,
achieving sufficiently strong focusing of midair ultrasound requires
engineering of the emitted wavefront, which is not possible with a single
transducer alone, in general. To this end, the following two strategies have
been adopted.

One is the use of phased arrays of airborne ultrasound transducers. Since its
advent [18, 19], many applications have been devised based on this technique.
The most prominent advantage of this approach is that ultrasound fields with a
huge variety in spatial distributions can be promptly generated by
electronically controlling the phase delays of emissions from individual
transducers. This feature is particularly beneficial for applications that
require real-time reconfiguration of the generated ultrasound field. However,
this approach requires numerous transducers to form a satisfactorily large
ultrasound emission aperture. Most current airborne ultrasonic phased arrays
employ cylindrical transducers with a resonance frequency of 40 kHz because of
their relatively low attenuation through propagation. Among commercially
available products, the most common transducers of that resonance frequency
are those with a diameter of 10 mm [20, 21]. When constructing an emission
plane using those transducers, 100 pieces of them are required for a 100 mm
$\times$ 100 mm aperture. Implementing arrays of such a large number of
transducers with their emission individually controlled requires much work and
cost, especially when one wants a large aperture that can focus over a long
distance from the emission plane.

The other approach is physically forming an emission plane with a spatial
distribution of output phase or amplitude. The biggest disadvantage of this
approach is that the focal positions cannot be electronically changed as with
the phased array technique. Nevertheless, this approach is generally more
affordable and is easier to fabricate than the previous one. The strategies
for realizing planar distributions of output phases include emission surface
with designed uneven height [22, 23] and use of acoustic metasurfaces or
metamaterials [24, 25, 26, 27]. Although those methods do not require arrays
of emission-controlling circuits, they require relatively complicated and
minute fabrication processes, sometimes in a three-dimensional fashion.

Figure 1: Schematic depiction of our proposed strategy for creating a midair
ultrasound focus out of partially occluded ultrasound emission from a
flexurally vibrating plate.

###  1.2 Focusing via Amplitude Distribution of Emission and Remaining
Problems

Contrastingly, creating amplitude distribution on the emission plane is
relatively easy, where a planar incident wave is transformed into a desired
wave field via an amplitude mask with a spatial distribution of acoustic
transmittance. A concentric transmittance distribution known as the Freznel-
zone-plate (FZP) is a representative approach, which offers focusing of planar
incident waves on the center axis of the plate with a desired focusing depth
[28, 29, 30, 31]. However, this approach assumes that the incident wave is
planar. Therefore, a considerable space between the wave source and the FZP-
based amplitude masks is required, which results in the need for a
considerable space behind the mask in creating a large ultrasound emission
aperture based on this approach.

To overcome this problem, we previously demonstrated an FZP-based focusing
method, where an array of airborne ultrasound transducers all driven in the
same phase serve as a spacious source of a planar wave [32]. An FZP is placed
just above the transducers to generate an intense midair ultrasound focus in
the same way as with methods employing FZPs for planar incident waves. This
method can construct focusing ultrasound apertures with side lengths of
several hundreds of millimeters with a configuration where virtually no space
between the ultrasound source and the amplitude mask is required. A planar
array of transducers driven in phase was adopted to realize an approximated
planar wave incidence with that large aperture, just above the emission plane.
The FZP here is fabricated from an acrylic plate that was processed with a
laser-machining apparatus with millimeter precision, which is much more
affordable than the processing and materials required for fabricating planes
with uneven height or acoustic metamaterials. However, arranging thousands of
transducers is still costly and may be an obstacle that may prevent this
technique from being applied to the fabrication of an even larger emission
plane. If such a huge emission plane for an intense midair ultrasound field is
realized, constructions of upsized versions of all current application systems
to a whole-room scale can be materialized, by which many new application
scenarios will emerge.

###  1.3 Motivation and Contribution of the Study

The goal of this study is to establish a method that can potentially create a
meter-order ultrasonic emission plane generating a midair ultrasound focus at
a desired position. To this end, we conceived of utilizing a monolithic
vibrating plate as an ultrasound source and partially covering its emission
similarly to the FZP-based techniques (Fig. 1). Creating such a vibrating
plate is so readily done with a single transducer placed on the plate, and the
plate can be affordably upsized. In this study, we drive a square duralumin
plate supported by a single Langevin ultrasonic transducer driven in
longitudinal vibration mode. This construction strategy of ultrasound emission
from a rigid body where a single Langevin transducer is attached to a plate is
found in preceding studies [33, 34]. The novelty of this study is that a newly
defined problem is handled where a midair ultrasound focus is to be created
out of incident waves that have phase and amplitude distribution on the
amplitude mask, which correspond to the positions of nodes and antinodes on
the vibrating plate.

The technical contribution of this paper is as follows:

  * •

conceptualization of the aforementioned new focusing method based on partial
occlusion of emission from a flexurally vibrating plate

  * •

derivation of a designing method of amplitude masks over the plate

  * •

experimental validation of successful midair focusing based on the proposed
strategy

In the following parts of the paper, we first describe the physical modeling
of the flexurally vibrating plate as an ultrasound emission source. Next, we
derive a design algorithm for amplitude masks based on this modeling. Then, we
explain the experimental apparatus composed of a vibrating plate activated by
a Langevin ultrasound transducer supporting the plate from its bottom and
fabricated amplitude mask covering the plate. Finally, we show the result of
ultrasound field measurement, in which midair ultrasound foci are successfully
generated as intended at desired positions. We expect that the proposed method
can potentially be one of the new standard methods for system construction for
generating intense midair focused ultrasound because of its simplicity,
affordability, and readiness for being upsized.

##  2 Method

###  2.1 Modeling of Ultrasound Emission Sources

We begin with modeling the flexural vibration plate as a two-dimensional array
of point sources of pressure vibration. A plate vibrating with a single
certain flexural mode contains nodes and antinodes on its surface. We assume
that the individual equivalent point sources on a plate have their emission
amplitudes being proportional to the vibrating amplitude of the plate at the
source positions. We also assume that the emission phases of the sources are
the same as those of the vibration of the plate at the source positions. The
validity of this assumption is later demonstrated by acoustic measurement and
numerical simulation results.

###  2.2 Designing Method of Amplitude Masks for Focusing

Let $\bm{r}_{t}=(x_{t},y_{t},0)$ be a position of the equivalent point source
on the plate and $\theta_{t}(\bm{r}_{t})$ be the emission phase delay of the
source at $\bm{r}_{t}$, where the coordinate system is defined so that the
origin is located on the center of the plate surface (Fig. 1). Here, the value
of $\theta_{t}(\bm{r}_{t})$ is ideally either 0 or $\pi$ (note that if this is
not the case for actual vibrators, the following method for designing
amplitude masks is still valid.) When the desired focal position is given as
$\bm{r}_{f}=(x_{f},y_{f},z_{f})$, the criteria of creating an amplitude mask
is realizing a large ultrasound amplitude at $\bm{r}_{f}$ out of partial
emission from the sources in a manner that those emissions can constructively
interfere at the focal position.

With $k$ denoting the wavenumber of ultrasound emission in the air, the phase
delay of ultrasound observed at the focal position, which is emitted from a
source located at $\bm{r}_{t}$ is given as

$\theta_{d}(\bm{r}_{t})=k||\bm{r}_{t}-\bm{r}_{f}||,$ (1)

where $||\cdot||$ denotes the vector norm of $\cdot$. In conventional FZP-
based mask designing procedures, the value of $\theta_{t}(\bm{r}_{t})$ is
uniform at any position on the plate. For this case, the amplitude mask is
designed with a simple criterion: according to quantization of
$\theta_{d}(\bm{r}_{t})$ by $\pi$ after phase wrapping, where to perforate in
the mask is determined. This situation is understood as that the emissions
with similar phase delays at the focal points are permitted, resulting in
intense ultrasound amplitude exclusively at the focal position. Concentric
mask patterns commonly created on FZPs are the outcome of those phase-
quantization procedures.

Figure 2: The designing method for the amplitude mask based on the calculation
of phase delays at the focal position from each emission point. All phase
graphs are drawn after being wrapped by $2\pi$.

Due to the flexural vibration on the plate yielding position-dependent
emission phase delays, in this study, the phase delay of the emissions from
$\bm{r}_{t}$ at the focus is not equal to $\theta_{d}(\bm{r}_{t})$. The total
phase delay $\theta_{s}(\bm{r}_{t})$ observed at the focal position, is given
as the sum of the emission phase delay $\theta_{t}(\bm{r}_{t})$ and
propagation phase delay $\theta_{d}(\bm{r}_{t})$. Therefore,

$\theta_{s}(\bm{r}_{t})=\theta_{t}(\bm{r}_{t})+\theta_{d}(\bm{r}_{t})$ (2)

holds. The above quantization criterion is again adopted here, finally giving
a design rule for binary mask amplitude distributions $P(\bm{r}_{t})$:

$P(\bm{r}_{t})=\left\\{\begin{array}[]{cc}1,&2n\pi\leq\theta_{s}(\bm{r}_{t})-\alpha<(2n+1)\pi\\\
0,&(2n+1)\pi\leq\theta_{s}(\bm{r}_{t})-\alpha<2(n+1)\pi\end{array}\right.,$
(3)

where $\alpha\in[0,2\pi]$ denotes a threshold value of the phase and $n$
denotes an integer that can be any of negative, zero, or positive. A designed
amplitude mask is supposed to block off the incident ultrasound at
$\bm{r}_{t}$ where $P(\bm{r}_{t})=0$, and to let the ultrasound travel through
it where $P(\bm{r}_{t})=1$. Note that the values of $\theta_{d}(\bm{r}_{t})$
and $\theta_{s}(\bm{r}_{t})$ here are not wrapped by $2\pi$. Here, the
absolute (not relative) value of $\theta_{s}(\bm{r}_{t})$ is essentially
indeterminable: an arbitrary constant phase shift can be added on all values
of $\theta_{t}(\bm{r}_{t})$ because there is no phase origin for
$\theta_{t}(\bm{r}_{t})$. Also, the resulting focal intensity relies on values
of $\alpha$. Therefore, in this study, we defined the value of
$\theta_{t}(\bm{r}_{t})$ as phase delays of the surface vibration from the
driving signal of the transducer, which is measured in an experiment described
in the following section. We set the value of $\alpha$ so that the focal
amplitude becomes the largest, which is calculated with the numerical
simulation method described in section 4 while varying the value of $\alpha$.
The whole calculation processes are schematically depicted in Fig. 2.

##  3 Experimental Setting

###  3.1 Composition of Experimental Apparatus

Figure 3 shows the constructed experimental apparatus containing a cylindrical
Langevin ultrasonic transducer with a resonance frequency of 28 kHz
(HEC-3028P4B, Honda Electronics Co., Ltd., Japan), a square duralumin
vibration plate with a thickness of 1 mm, and a conical acoustic horn made of
duralumin that combines the tip of the transducer and the vibrating plate as
ultrasound emitting components. The top and bottom diameters of the horn were
6 mm and 30 mm, respectively. The center of the vibration plate contained a
through hole of 3.2 mm in diameter, where the horn tip was bolted. Those
components were mounted on an external aluminum frame via a metallic jig that
was in contact with the sides of the horn on the nodal position to supress
vibration absorption by the frame. A fabricated amplitude mask was placed on
the top of the frame with no direct contact with the vibrating plate.

###  3.2 Dimension Design of the Vibrating Components

According to the resonance frequency of the transducer, we determined the
dimensions of the acoustic horn and the vibrating plate using numerical
simulations based on the finite-element method. The length of the horn was
determined so that a single node where the holding jig should be in contact
was exhibited at the vibrating mode of 28 kHz. The side length of the square
vibrating plate was determined as 87.6 mm. We experimentally verified that the
whole vibrating system where the transducer, the acoustic horn, and the
vibrating plate were coalesced, had its forced resonance output peak around
the resonance frequency of the transducer.

###  3.3 Fabrication of the Amplitude Masks

We adopted a 2-mm-thick acrylic plate as the material for the amplitude mask.
We cut out the plate using a laser machining apparatus (Etcher Laser Pro,
smartDIYs Co., Ltd., Japan). The mask pattern was constructed by an array of
square perforations with a side length of 2 mm, which is calculated from the
result of the following source phase distribution measurement and phase
quantization formulated in eq. (3). Adjacent perforations are incorporated to
form a large transmission area in the plate. In addition, several parts that
were isolated from the edge of the pattern as a result of pattern calculation
were manually adjusted so that they were in contact with the plate.

###  3.4 Measurement Procedures

We set the driving frequency of the vibration system to 27,877 Hz throughout
the following acoustic measurement experiments. We used a standard microphone
system (1/8-in. microphone, type 4138-A-015; pre-amplifier, type 2670;
condition amplifier, type 2690-A; all products of Hottinger, Brüel and Kjær,
Denmark). This microphone has an almost flat frequency response from 6.5 Hz to
140 kHz. The directivity of the microphone is limited within 3 dB across the
elevation angle of the incident wave ranging from 0 to 90 degrees. The
measured signal was sent to a lock-in amplifier (LI5640, NF Corporation,
Japan) to calculate the phase and amplitude of the frequency component in the
measurement that matched the sinusoidal driving signal provided by a function
generator as a reference signal. The driving signal was also provided from the
same function generator in parallel, and was amplified via a bipolar amplifier
(HSA4052, NF Corporation, Japan), and the driving voltage of the transducers
was set to 3.6 V in RMS value. The microphone scanned two-dimensionally on a
plane that was parallel to the xy-plane defined by the coordinate system in
Fig. 1 using combined two-axis linear actuators (EZSM4D030AZAC and
EZSM6D070AZAC, Oriental Motor Co., LTD., Japan). The whole experimental setup
is schematically depicted in Fig. 4. We used a PC for the storage of data that
was transmitted from a digital storage oscilloscope.

Figure 3: Fabricated experimental apparatus.

Figure 4: Schematic depiction of the experimental setup and signal flows in
acoustic measurement.

##  4 Experimental Results

Figure 5: Measured pressure amplitude distribution (Upper Figure) and phase
distribution (Lower Figure) near the vibration surface of the plate.

###  4.1 Surface Vibration Measurement of the Plate and Fabrication of the
Amplitude Masks

We first measured surface pressure distribution just above the vibrating
plate, which is necessary for the designing of the amplitude mask. We scanned
a plane located 2 mm above the plate with spatial intervals of 2 mm,
corresponding to the spatial resolution of the mask-designing procedure. The
size of the scanning area was 88 mm on each side.

Figure 5 shows the obtained amplitude and phase distributions of pressure
waveform over the vibrating plate. Note that the phase distribution shown here
is not the phase delay of the plate vibration but the phase advance of that
compared with the reference signal fed to the lock-in amplifier. Based on this
measurement, we created five amplitude masks as shown in Fig. 6. The focal
positions are
$\bm{r}_{f1}=(0,0,100),\bm{r}_{f2}=(30,0,100),\bm{r}_{f3}=(30,-30,100),\bm{r}_{f4}=(50,0,100),$
and $\bm{r}_{f5}=(50,-50,100),$ all indicated in millimeters. In the upper row
of Fig. 7, we indicate all calculated amplitude mask patterns for the focal
positions from $\bm{r}_{f1}$ to $\bm{r}_{f5}$.

Figure 6: Example of mask pattern calculation (upper figure) and fabricated
acrylic amplitude mask plate (lower figure) for the focal position of
$\bm{r}_{f1}$ = (0 mm, 0 mm, 100 mm). White and black regions in the pattern
correspond to the region where ultrasound is transmitted and is blocked off,
respectively. As stated in the main text, bridging ’close’ elements that were
not indicated in the mask patterns in the upper figure were manually added to
actual masks to prevent some ’close’ regions from being isolated from the
surrounding parts of the plate.

Figure 7: Calculated amplitude mask patterns (upper row), measured ultrasonic
pressure amplitude distributions (middle row), and numerically calculated
pressure amplitude distributions (lower row). Each column corresponds to the
focal possition of $\bm{r}_{f1},\ldots,\bm{r}_{f5}$ from left to right. All
focal coordinates are in millimeters.

###  4.2 Acoustic Field Measurement and Numerical Simulations

Next, we placed each amplitude mask over the vibrating plate and scanned the
microphone in a square region with a side length of 200 mm, which was located
100 mm above the plate with a scanning interval of 4 mm. Because the
wavelength of 27,877 Hz ultrasound in air is 12.2 mm, we consider this
scanning interval to be sufficiently small. The size of the scanning area was
200 mm on each side.

The measurement results for each amplitude mask are shown in the middle row of
Fig. 7. Note that the captured waveforms included weak harmonics of the
driving frequency of the transducer due to the nonlinearity of air.
Nevertheless, the RMS values of the captured waveforms and that of the driving
frequency component in that waveform extracted by the lock-in amplifier showed
little difference. Therefore, we show the latter values as pressure amplitude
in the figures. At the intended focal position, intensified ultrasound
amplitude is observed for all cases. The diameters of the foci are
approximately 20-30 mm. Around the foci, several artifacts are observed whose
intensities are not negligibly small.

To verify the assumption that the flexural vibrating plane can be modeled as a
set of small point sources with phase distributions, we performed numerical
simulations of generated ultrasound field. By assuming omnidirectivity of the
point sources, based on the principle of superposition, the resulting complex
amplitude field $p_{\mathrm{sim}}(\bm{r})$ with respect to $\bm{r}$ denoting
an arbitrary position in the air is given as

$p_{\mathrm{sim}}(\bm{r})=\sum_{m}A_{m}\frac{e^{-jk||\bm{r}-\bm{r}_{m}||}}{||\bm{r}-\bm{r}_{m}||},$
(4)

where $j=\sqrt{-1}$ is the imaginary unit, $m$ is an index of point sound
sources, $A_{m}$ is complex emission amplitude of the source, and $\bm{r}_{m}$
is the source position. We calculated the amplitude distributions for each
amplitude mask based on Eq. (4), with the values of $A_{m}$ determined
according to the surface pressure measurement shown in Fig. 5 and the masking
pattern.

The lower row of Fig. 7 shows the simulation results. It is confirmed that the
results of simulations and measurements show good agreement. These results
indicate that the point source modeling approach adopted in our study
faithfully reflected actual physical phenomena engendered with our apparatus.
It is also demonstrated that the aforementioned simulation procedures can
accurately predict the resulting ultrasound field out of a pair of a vibration
mode of a plate and an amplitude masking pattern on the plate.

##  5 Discussions

###  5.1 Artifacts Superimposed onto the Desired Focal Amplitude Distribution

As stated, the intensity of some artifacts is relatively large, which may be
undesirable in practical situations. Figure 8 shows the measurement and
numerical simulation results of ultrasound amplitude distribution where no
amplitude mask was placed on the vibrating plate. The results show that the
artifact patterns around the foci are similar to this mask-free amplitude
pattern. This fact is understood as follows. partially covering the emission
from the plate is equivalent to adding some spatial interference to the
original emission pattern of the plate shown in Fig. 8. This spatial
interference can create a new focusing point as desired, but will not
completely delete the original amplitude image, which inevitably is
superimposed to the focal pattern.

Figure 8: Pressure amplitude pattern obtained via measurement (left figure)
and numerical simulation (right figure) where no amplitude mask is placed over
the vibrating plate.

Next, we show the numerical simulation results for amplitude distribution on
the $xz$-plane in Fig. 9, which was unable to be scanned with the actuators
that we had. According to the results, a small region with intense ultrasonic
power conversion is observed just above the center of the plate. This is
because the vibration mode had a spatial phase distribution similar to
concentric rings, which was expected to yield an on-axis constructive
ultrasound beam like the Bessel beam [5].

The resulting vibrating mode on the plate may be somewhat inappropriate in a
practical context because of a few artifacts. A different vibrating mode such
as the one with checker-board-like phase distribution may exhibit much weaker
artifacts around the focal position. In addition, it may be the case that the
artifact could be partially explained by the grating lobe effect of arrayed
emitters where unintentional radiation directivities occur in certain
directions due to spatial intervals between array elements longer than half
the wavelength. Therefore, a two-dimensional phase distribution mode with
sufficiently short inter-node distances would be one good solution for
reducing artifacts and thereby improving the focusing efficiency.

Figure 9: Pressure amplitude simulation on the $xz$-plane with no amplitude
mask placed over the vibrating plate (left figure), and that with the
amplitude mask for the focus at $\bm{r}_{f4}$ (right figure).

###  5.2 Limitation and Possible Improvement of Current Apparatus for
Practical Use

The current apparatus drives the vibrating plate via a very small single-
bolted joint surface attached to the acoustic horn. We found that excitation
via this joint surface with higher driving voltage often resulted in the
gradual relaxation of the bolt. Due to this, the whole experiments were
conducted while suppressing the excitation voltage within relatively a small
value.

Because the main motivation of our experiments is to experimentally
demonstrate the validity of our strategy of partial covering of flexural
emission for midair ultrasound focusing, the emission aperture in the
experiments was kept relatively small. If one wants to form a larger emission
plane out of our technique, the single-point support of the vibrating plate
adopted in the experiment is not suitable because the plate will become
heavier for larger apertures. To achieve a more stable operation with such a
large vibrating plate, driving multiple antinodes of the desired mode with
several harmonically driven transducers that also support the vibration plate
may be a solution for this problem.

Another important aspect is the choice of the plate material. Current
material, the aluminum plate might not be the best choice when the plate
becomes larger and is driven with greater displacement. For those cases,
thermal dissipation inside the plate may be crucial, so more efficient
(lossless) material may be needed to be used. As another solution for this,
attaching small thermal components serving as heat sinks on nodes of the plate
could be applicable for promoting heat convection to the air without lowering
the vibration power of the plate.

##  6 Conclusions

In this study, we proposed a method that enables the construction of an
ultrasound emission aperture for creating a midair ultrasonic focus that is
composed of a monolithic vibration plate and a planar amplitude mask that
partially occludes the emission of the plate. In designing processes of
amplitude masks, we modeled the emission from the plate as a set of small
point sources and derived an amplitude distribution calculation method based
on phase-delay quantization that is an extension of the conventional FZP
designing criteria. We fabricated amplitude masks based on that procedure and
placed them above the vibrating plate to create midair foci of ultrasound. We
measured the generated ultrasound amplitude distribution and demonstrated the
successful generation of ultrasound foci at intended positions. Results of
numerical simulations and acoustic measurement showed good agreement, which
indicates the validity of our modeling strategy of a vibrating plate as a set
of point sources and the designing algorithm of amplitude masks.

The aperture of the current experimental apparatus is 87.6 mm in side length,
and the focal depth is only 100 mm. To fabricate an upsized version,
supporting and activating the plate with multiple synchronously driven
transducers is one of the reasonable solutions. Even in those cases, the
proposed method is expected to be much more affordable than conventional
methods, where minute fabrication of acoustic metamaterials or compactly
arranged thousands of transducers in the emission plane are required. We
consider that the focusing strategy demonstrated in this paper is currently
one of the most realistic potential compositions of meter-order emission
apertures. It is expected that new applications such as acoustic levitation or
noncontact actuation in a whole room scale can be materialized based on our
technique in the future. To demonstrate the possibility of such applications,
the physical construction of a larger emission plane remains our next
challenge. From a viewpoint of practicality, establishing a method of
electronically controlling amplitude distribution on the mask is also an
important issue.

## References

  * [1] L. V. King, ”On the Acoustic Radiation Pressure on Spheres, ” Proc. R. Soc. Lond., A 147, pp. 212–-240, 1934.
  * [2] T. G. Wand and C. P. Lee, ”Radiation Pressure and Acoustic Levitation,” in Nonlinear Acoustics, Chap. 6, edited by M. F. Hamilton and D. T. Blackstock, Academic Press, 1998.
  * [3] C. Eckart, ”Vortices and Streams Caused by Sound Waves,” Physical Review, 73, pp.68–76, 1948.
  * [4] W. L. Nyborg, ”Acoustic Streaming Equations: Laws of Rotational Motion for Fluid Elements,” J. Acoust. Soc. Am., 25 (5), pp.938-–944, 1953.
  * [5] K. Hasegawa, L. Qiu, A. Noda, S. Inoue, and H. Shinoda, ”Electronically Steerable Ultrasound-Driven Long Narrow Air Stream,” Applied Physics Letters, 111, 064104, 2017.
  * [6] P. J. Westervelt, ”Parametric Acoustic Array,” J. Acoust. Soc. Am., 35 (4), pp. 535-–537, 1963.
  * [7] M. Yoneyama, J. Fujimoto, Y. Kawamo, and S. Sasabe, ”The Audio Spotlight: An Application of Nonlinear Interaction of Sound Waves to a New Type of Loudspeaker Design,” J. Acoust. Soc. Am., 73 (5), pp. 1532-–1536, 1983.
  * [8] A. Marzo, A. Barnes, and B. W. Drinkwater, ”TinyLev: A multi-emitter single-axis acoustic levitator,” Rev. Sci. Instrum., 88 (8), 085105, 2017.
  * [9] I. Ezcurdia, R. Morales, M. A. B. Andrade, and A. Marzo, ”LeviPrint: Contactless Fabrication using Full Acoustic Trapping of Elongated Parts,” in ACM SIGGRAPH 2022 Conference Proceedings (SIGGRAPH ’22), Article 52, pp.1–9, 2022.
  * [10] S. Inoue, S. Mogami, T. Ichiyama, A. Noda, Y. Makino, and H. Shinoda, ”Acoustical boundary hologram for macroscopic rigid-body levitation,” Journal of the Acoustical Society of America, 1. 145, pp. 328–337, 2019.
  * [11] R. Hirayama, G. Christopoulos, D. Martinez Plasencia, and S. Subramanian, ”High-speed acoustic holography with arbitrary scattering objects,” Sci. Adv., 8, Vol 8, Issue 24, 2022.
  * [12] A. Marzo, S. Seah, B. Drinkwater, et al., ”Holographic acoustic elements for manipulation of levitated objects,” Nat Commun 6, 8661, 2015.
  * [13] I. Rakkolainen, E. Freeman, A. Sand, R. Raisamo, and S. Brewster, ”A survey of mid-air ultrasound haptics and its applications,” IEEE Trans Haptics, vol. 14, no. 1, pp. 2–19, 2021.
  * [14] D. Hajas, D. Pittera, A. Nasce, O. Georgiou, and M. Obrist, ”Mid-air haptic rendering of 2D geometric shapes with a dynamic tactile pointer,” IEEE Trans Haptics, vol. 13, no. 4, pp. 806-817, 2020.
  * [15] R. Takahashi, K. Hasegawa, and H. Shinoda, ”Tactile Stimulation by Repetitive Lateral Movement of Midair Ultrasound Focus,” IEEE Transactions on Haptics, vol. 13, no. 4, pp. 334-342, 2020.
  * [16] K. Hasegawa, L. Qiu, and H. Shinoda, ”Midair Ultrasound Fragrance Rendering,” IEEE Transactions on Visualization and Computer Graphics, vol. 24, no. 4, pp. 1477-1485, 2018.
  * [17] K. Nagata and K. Hasegawa, ”Suppression of Short Range Exposure to Infectious Aerosols using Multiple Paths of Midair Ultrasound Acoustic Streaming”, Aerosol Science and Technology, pp.1–16. https://doi.org/10.1080/02786826.2024.2345156, 2024.
  * [18] T. Iwamoto, M. Tatezono, and H. Shinoda, ”Non-contact Method for Producing Tactile Sensation Using Airborne Ultrasound,” in Proc. of Eurohaptics 2008, pp.504-513, 2008.
  * [19] T. Hoshi, M. Takahashi, T. Iwamoto, and H. Shinoda, ”Noncontact Tactile Display Based on Radiation Pressure of Airborne Ultrasound,” IEEE Trans. on Haptics, Vol. 3, No. 3, pp.155-165, 2010.
  * [20] S. Suzuki, S. Inoue, M. Fujiwara, Y. Makino, and H. Shinoda, ”AUTD3: Scalable Airborne Ultrasound Tactile Display,” IEEE Transactions on Haptics, Vol. 14, No. 4, pp. 740-749, 31 March 2021.
  * [21] A. Marzo, T. Corkett and B. W. Drinkwater, ”Ultraino: An Open Phased-Array System for Narrowband Airborne Ultrasound Transmission,” IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, vol. 65, no. 1, pp. 102-111, 2018.
  * [22] K. Melde, A. G. Mark, T. Qiu, and P. Fischer, ”Holograms for Acoustics,” Nature, 537, pp.518-522, 2016.
  * [23] S. Polychronopoulos and G. Memoli, ”Acoustic Levitation with Optimized Reflective Metamaterials,” Scientific Reports, 10, 4254, 2020.
  * [24] R. Al. Jahdali and Y. Wu, ”High Transmission Acoustic Focusing by Impedance-Matched Acoustic Meta-Surfaces,” Applied Physics Letters, 108, 031902, 2016.
  * [25] S. D. Zhao, A. L. Chen, Y. S. Wand, and C. Zhang, ”Continuously Tunable Acoustic Metasurface for Transmitted Wavefront Modulation,” Phys. Rev. Applied, 10, 054066, 2018.
  * [26] A.-C. Hladky-Hennion, J. O. Vasseur, G. Haw, C. Croënne, L. Haumesser, and A. N. Norris, ”Negative refraction of acoustic waves using a foam-like metallic structure,” Appl. Phys. Lett, 102 (14), 144103, 2013.
  * [27] L. Zhao, E. et al., ”Ultrasound beam steering with flattened acoustic metamaterial Luneburg lens,” Appl. Phys. Lett., 116 (7), 071902, 2020.
  * [28] D. Schindel, A. Bashford, and D. Hutchins, ”Focussing of ultrasonicvwaves in air using a micromachined fresnel zone-plate,” Ultrasonics 35, pp.275-285, 1997.
  * [29] X. Xia, Y. Li, F. Cai, H. Zhou, T. Ma, and H. Zheng, ”Ultrasonic tunable focusing by a stretchable phase-reversal Fresnel zone plate,” Applied Physics Letters, 117, 021904, 2020.
  * [30] S. Pérez-Lopéz, J. M. Fuster, and P. Candelas, ”Spatio-temporal ultrasound beam modulation to sequentially achieve multiple foci with a single planar monofocal lens,” Scientic Reports, 11, 13458, 2021.
  * [31] S. Hur, H. Choi, G. H. Yoon, N. W. Kim, D.-G. Lee, and Y. T. Kim, ”Planar ultrasonic transducer based on a metasurface piezoelectric ring array for subwavelength acoustic focusing in water,” Scientific Reports 12, 1485, 2022.
  * [32] M. Kitano and K. Hasegawa, ”Airborne Ultrasound Focusing Aperture with Binary Amplitude Mask Over Planar Ultrasound Emissions,” Journal of Applied Physics, 133, 144901, 2023.
  * [33] G. V. Selicani, and F. Buiochi, ”Stepped-plate ultrasonic transducer used as a source of harmonic radiation force optimized by genetic algorithm,” Ultrasonics, Vol. 116, 106505, 2021.
  * [34] Y. Ito, R. Kato, and A. Osumi, ”Examinations of behavior of liquid irradiated with highintensity aerial ultrasonic waves in a long pore,” Jpn. J. Appl. Phys., 52, 7S, 07HE12, 2013.


# Planar Bichromatic Bottleneck Spanning Trees 111This work was partially
supported by Grant 2016116 from the United States – Israel Binational Science
Foundation. Mitchell was partially supported by NSF (CCF-1526406).

A. Karim Abu-Affash Software Engineering Department, Shamoon College of
Engineering, Beer-Sheva 84100, Israel<EMAIL_ADDRESS>Sujoy Bhore
Department of Computer Science, Ben-Gurion University, Beer-Sheva 84105,
Israel<EMAIL_ADDRESS> Paz Carmi Department of Computer Science, Ben-
Gurion University, Beer-Sheva 84105, Israel<EMAIL_ADDRESS> Joseph S.
B. Mitchell Department of Applied Mathematics and Statistics, Stony Brook
University, Stony Brook, NY, USA<EMAIL_ADDRESS>
###### Abstract

Given a set $P$ of $n$ red and blue points in the plane, a _planar bichromatic
spanning tree_ of $P$ is a spanning tree of $P$, such that each edge connects
between a red and a blue point, and no two edges intersect. In the bottleneck
planar bichromatic spanning tree problem, the goal is to find a planar
bichromatic spanning tree $T$, such that the length of the longest edge in $T$
is minimized. In this paper, we show that this problem is NP-hard for points
in general position. Moreover, we present a polynomial-time
$(8\sqrt{2})$-approximation algorithm, by showing that any bichromatic
spanning tree of bottleneck $\lambda$ can be converted to a planar bichromatic
spanning tree of bottleneck at most $8\sqrt{2}\lambda$.

##  1 Introduction

Let $P$ be a bi-colored set of red and blue points in the plane and let
$n=|P|$. A _bichromatic spanning tree_ of $P$ is a spanning tree of $P$ whose
edges are straight-line segments connecting between points of different
colors. A spanning tree is planar if its edges do not cross each other.
Borgelt et al. [15] studied the problem of computing a minimum-weight planar
bichromatic spanning tree, and showed that the problem is NP-hard. Moreover,
for points in general position, they gave an $O(\sqrt{n})$-approximation
algorithm, and for points in convex position, they gave an exact cubic-time
algorithm. Biniaz et al. [11] studied the problem of computing a maximum-
weight planar bichromatic spanning tree and gave a $(1/4)$-approximation
algorithm for the problem.

Algorithmic problems on bichromatic geometric input have appeared in many
problems, including, e.g., trees [1, 12, 15], matchings [13, 17], and
partitionings [18]. Often the bichromatic input is referred to as “red-blue”
input, e.g. in red-blue intersection [4, 22], red-blue separation [9, 14, 16,
19], and red-blue connection problems [5, 10]. For a survey of many geometric
problems on bichromatic (red-blue) points, see Kaneko and Kano [20].

Many of the structures studied in computational geometry are planar, including
minimum spanning trees, minimum weight matchings, Delaunay/Voronoi diagrams,
etc. Therefore, the planarity requirement is quite natural, and indeed many
researchers have considered geometric problems dealing with crossing-free
configurations in the plane; see, e.g. [2, 3, 6, 7, 8].

In this paper, we study the problem of computing a bottleneck planar
bichromatic spanning tree of $P$, in which we seek a planar bichromatic
spanning tree that minimizes bottleneck, i.e., the length of the longest edge.
To the best of our knowledge, this problem has not been considered before.

Our results. In Section 2, we prove that the problem of computing a bottleneck
planar bichromatic spanning tree is NP-hard. Our proof is based on a reduction
from the planar 3-SAT problem, and is influenced by the proof of Borgelt et
al. [15]. As a corollary we obtain that the problem does not admit a PTAS.
Next, in Section 3, we present a polynomial-time algorithm for computing a
planar bichromatic spanning tree of bottleneck at most $8\sqrt{2}$ times the
bottleneck of a bottleneck planar bichromatic spanning tree. We first compute
a bottleneck bichromatic spanning tree having bottleneck $\lambda$ that may
have crossings. Then, we use the length $\lambda$ to define a partition of the
plane into convex cells, and to partition $P$ into subsets according to these
cells. Next, we construct planar bichromatic trees for each subset, and we
connect these trees to obtain a planar bichromatic spanning tree of $P$. We
show that this tree has a bottleneck at most $8\sqrt{2}\lambda$.

##  2 Hardness Proof

In this section, we prove the following theorem.

######  Theorem 2.1.

Let $P$ be a set of $n$ red and blue points in the plane. Then, computing a
bottleneck planar bichromatic spanning tree of $P$ is NP-hard.

###### Proof.

We adapt the proof of Borgelt et al. [15], making modifications necessary to
address the bottleneck version. For completeness, we explain the ingredients
required for the proof.

The proof is based on a reduction from the planar 3-SAT problem. Given a 3-CNF
formula $F$ with $n$ variables $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ and $m$
clauses $Y=\\{C_{1},C_{2},\ldots,C_{m}\\}$, let $G_{F}=(V,E)$ be the graph of
$F$, i.e., $V=X\cup Y$ and $E=\\{(x_{i},C_{j}):x_{i}\mbox{ appears in
}C_{j}\\}$. If $G_{F}$ is planar, then $F$ is called a planar 3-CNF formula.
The planar 3-SAT problem is to determine whether a given planar 3-CNF formula
$F$ is satisfiable; the problem is NP-complete [21].

Let $F$ be a planar 3-SAT formula. We construct, in polynomial time, a set $P$
of red and blue points in the plane, such that $F$ is satisfiable if and only
if there exists a planar bichromatic spanning tree of $P$ of bottleneck 1.
Consider the graph $G_{F}$. It is well known that $G_{F}$ can be embedded in
the plane in polynomial time.

The construction is based on chains of pairs of red and blue points. We call
the pairs in the chain _sites_. The distance between the points in each site
is less than 1, and the distance between two points of different colors in
consecutive sites is exactly 1; see Figure 1(a). Now, for every two
consecutive sites, there are two possible edges to connect them: we either
connect the blue point of the first site with the red point of the second
site, or the other way around. Moreover, the chain is constructed in such a
way that if we connect the blue point in the leftmost site to the red point in
the next site, this forces the choice of connections in one direction along
the chain; see Figure 1(b).

Figure 1: A chain of red-blue sites.

Variables. Each variable $x_{i}\in X$ is represented by a circular chain of
sites, a special red point $r_{i}$, and a red-blue path; see Figure 2. The
addition of the red-blue path to the variable gadget of [15] is required,
since without it the special red point $r_{i}$ can be connected to both sides
of the chain without increasing the bottleneck, which is not the case in the
minimum weight version. The red-blue path forces $r_{i}$ to be connected
exactly to one side.

Figure 2: The trees corresponding to the true and the false assignments of
$x_{i}$.

The sites on the circular chain are located on two (inner and outer) circles.
We locate the points in such a way that the distance between each consecutive
sites on the circular chain, the distance between $r_{i}$ and its neighboring
sites in the chain, and the distance between the endpoints of the red-blue
path and the chain is exactly 1. Moreover, the points are located such that,
there are only two possible optimal trees (i.e., planar bichromatic spanning
trees of bottleneck 1) of the points, depending on the connection of $r_{i}$
to the chain. In both trees, $r_{i}$ is connected to exactly one site of the
chain. We arbitrarily associate one of them with the assignment $x_{i}=T$, and
the other with the assignment $x_{i}=F$; see Figure 2. Thus, the value of
$x_{i}$ will determine the tree of these points, and vice virsa. Moreover, if
$x_{i}=T$ (resp., $x_{i}=F$), then the red points on the right (resp., on the
left) of the inner circle are free to be connected to points outside the
gadget, and the red points on the left (resp., on the right) of the inner
circle cannot be connected to points outside the gadget without crossing, and
vice versa.

Clauses. Each clause $C_{j}$ is represented by a single red point $r_{j}$ and
three chains that will be connected to the respective variables of $C_{j}$;
see Figure 3(a). The distance between $r_{j}$ and each chain is 1. In any
optimal tree, $r_{j}$ will be connected to at least one of the three chains.
However, it cannot be connected to any chain if all the chains are connected
to variables that are in the wrong state; see Figure 3(b).

Figure 3: The gadget corresponding to the clause $C_{j}$.

We connect between the variables and the clauses such that, in any optimal
tree, one of the three chains of the clause has to be connected to a red point
on the inner circle of the corresponding variable. Assume that $x_{i}$ appears
unnegated in a clause $C_{j}$ and negated in a clause $C_{k}$, i.e.,
$C_{j}=(x_{i}\vee\cdot\vee\cdot)$ and
$C_{k}=(\widetilde{x_{i}}\vee\cdot\vee\cdot)$. We connect the chain of $C_{j}$
that is respective to $x_{i}$ to a site on the right of the inner circle of
the gadget $x_{i}$, and we connect the chain of $C_{k}$ that is respective to
$x_{i}$ to a site on the left of the inner circle of the gadget $x_{i}$; see
Figure 4. This connection ensures that, if $x_{i}$ is assigned $T$, then the
red point on the right of the inner circle of $x_{i}$ is free to be connected
to the chain of $C_{j}$, and this connection can produce a path through the
chain that ends at $r_{j}$. On the other hand, if $x_{i}$ is assigned $T$,
then the red point on the left of the inner circle of $x_{i}$ cannot be
connected to the chain of $C_{k}$, which does not allow a connection between
the chain and $r_{k}$. The same argument holds when $x_{i}$ is assigned $F$.

Figure 4: The connection between the variable $x_{i}$ and the clauses $C_{j}$
and $C_{k}$.

Finally we need to connect all variables to each other by some fixed part of
the tree, because the whole construction needs to be a tree and not a forest.
These connections can easily be made using red-blue chains having distance at
most 1 between every two consecutive points in the path. Also, we need to make
sure that the distance between different parts of the construction is large
enough to avoid shortcuts. ∎

Notice that in the reduction we proved that if the 3-SAT formula is not
satisfiable, then any planar bichromatic spanning tree of $P$ has an edge of
length greater than 1. Actually, we can push the length of this edge to be
closed to $\sqrt{2}$. That is, we can draw the connection between each clause
and its corresponding variables, such that the distance between each chain of
the clause and the corresponding site on the inner circle of the variable is
1, and the distance between each chain of the clause and the sites on the
outer circle of the variable is at least $\sqrt{2}-\varepsilon$, for any
$0<\varepsilon<\sqrt{2}-1$; see Figure 4. This implies that the bottleneck
planar bichromatic spanning tree problem cannot be approximated within a
factor less than $\sqrt{2}$, unless $P=NP$.

######  Corollary 2.2.

The bottleneck planar bichromatic spanning tree problem cannot be approximated
within a factor less than $\sqrt{2}$, unless $P=NP$. In particular, there is
no PTAS (unless $P=NP$).

##  3 Approximation Algorithm

Let $P$ be a set of red and blue points in the plane and let $n=|P|$. Let $T$
be a bichromatic spanning tree of $P$ of minimum bottleneck ($T$ may have
crossings and can be computed in $O(n\log{n})$ time [12]). Let $\lambda$
denote the bottleneck of $T$, i.e., the length of the longest edge in $T$.
Notice that $\lambda$ is the lower bound for any bichromatic spanning tree of
$P$, in particular for any planar bottleneck bichromatic spanning tree of $P$.
In this section, we show how to compute a planar bichromatic spanning tree of
$P$, such that its bottleneck is at most $8\sqrt{2}\lambda$.

Our algorithm partitions the plane into disjoint cells satisfying the
following properties:

  1. 1.

Each cell is convex and contains points of both colors.

  2. 2.

In each cell, the distance between any two points is bounded by
$5\sqrt{2}\lambda$.

  3. 3.

The cells are connected, i.e., if we consider the graph with the cells as its
vertices and there is an edge between two cells if they are adjacent (sharing
a common boundary), then this graph is connected.

  4. 4.

We can construct a planar bichromatic spanning tree of the points in each cell
and we can connect them without crossings.

Assume, w.l.o.g., that $\lambda=1$. We begin by laying an axis-parallel grid,
such that each (square) cell is of edge length $3$ and the points of $P$ are
in the interior (not on the boundary) of these cells; see Figure 5. We say
that a cell $C_{i,j}$ is bichromatic if it contains points of both colors and
we say that $C_{i,j}$ is monochromatic (red or blue) if all of the points in
$C_{i,j}$ have the same color, otherwise, we say that $C_{i,j}$ is an empty
cell.

Figure 5: The grid partitioning the points of $P$.

Our algorithm consists of two stages. In Stage 1, we modify the grid cells to
satisfy properties (1)-(3), and, in Stage 2, we construct a planar bichromatic
spanning tree of the points in each cell and connect between these trees to
obtain a planar bichromatic spanning tree of $P$.

### Stage 1

In this stage, we consider the monochromatic cells and we partition and merge
portions of them in order to obtain a subdivision in which all cells are
convex and bichromatic. Let $C_{i,j}$ be a $3\times 3$ cell of the grid. Since
$C_{i,j}$ is a $3\times 3$ cell, $C_{i,j}$ is the union of 9 unit sub-cells,
labelled $C_{i,j}^{k}$, for $k=1,2,3,\dots,9$, as shown in Figure 6(a). Notice
that, since $C_{i,j}$ is a monochromatic cell, the points of $C_{i,j}$ are of
distance at most 1 from the boundary of $C_{i,j}$, and therefore,
$C_{i,j}^{5}$ is empty of points of $P$. The region $C_{i,j}\setminus
C_{i,j}^{5}$ is the union of four trapezoids ${{\cal{T}}}_{i,j}^{l}$,
${{\cal{T}}}_{i,j}^{r}$, ${{\cal{T}}}_{i,j}^{t}$, and ${{\cal{T}}}_{i,j}^{b}$,
such that ${{\cal{T}}}_{i,j}^{l}$ (resp., ${{\cal{T}}}_{i,j}^{r}$,
${{\cal{T}}}_{i,j}^{t}$, and ${{\cal{T}}}_{i,j}^{b}$) is the trapezoid
obtained by connecting the left (resp., right, top, and bottom) corners of
$C_{i,j}$ by diagonals to the left (resp., right, top, and bottom) corners of
$C_{i,j}^{5}$; see Figure 6(b).

Figure 6: (a) The 9 unit sub-cells of cell $C_{i,j}$. (b) The trapezoids
${{\cal{T}}}_{i,j}^{l}$, ${{\cal{T}}}_{i,j}^{r}$, ${{\cal{T}}}_{i,j}^{t}$, and
${{\cal{T}}}_{i,j}^{b}$.

##### Stage 1.1

In this stage, we introduce a directed graph $G$ in which the vertices are the
monochromatic cells and the edges are defined as follows. Let $C_{i,j}$ be a
monochromatic cell, and let ${{\cal{N}}}(C_{i,j})=\\{C_{i,j-1}$, $C_{i,j+1}$,
$C_{i-1,j},C_{i-1,j+1}\\}$ be the set of cells that share a grid edge with
$C_{i,j}$. Let $C\in{{\cal{N}}}(C_{i,j})$ be a monochromatic cell and assume,
w.l.o.g., that $C=C_{i,j+1}$. There is a directed edge from $C_{i,j}$ to
$C_{i,j+1}$ if and only if $C_{i,j}$ and $C_{i,j+1}$ are of different colors
and the trapezoid ${{\cal{T}}}_{i,j}^{r}$ is not empty of points of $P$; see
Figure 7.

Figure 7: Directed edges between monochromatic cell $C_{i,j}$ and its
monochromatic neighbors ($C_{i,j-1}$, $C_{i-1,j}$, $C_{i,j+1}$).

##### Stage 1.2

In this stage, we modify the grid cells by partitioning and merging some of
the monochromatic cells with their neighbors, guided by the directed edges
introduced in Stage 1.1. Before describing how to modify the grid cells, we
describe the following _cell partition procedure_ that we will apply in this
stage to the empty and some of the monochromatic cells.

Cell partition procedure. For a monochromatic cell $C_{i,j}$, partition
$C_{i,j}\setminus C_{i,j}^{5}$ into trapezoids ${{\cal{T}}}_{i,j}^{l}$,
${{\cal{T}}}_{i,j}^{r}$, ${{\cal{T}}}_{i,j}^{t}$, and ${{\cal{T}}}_{i,j}^{b}$,
and merge them with the cells $C_{i,j-1}$ , $C_{i,j+1}$, $C_{i-1,j}$, and
$C_{i+1,j}$, respectively; see Figure 8(b).

Figure 8: (a) $d_{in}(C_{i,j})=0$ and $d_{out}(C_{i,j})>0$. (b) Partitioning
and merging $C_{i,j}$ with its neighbors.

Let $d_{in}(C_{i,j})$ (resp., $d_{out}(C_{i,j})$) denote the in-degree (resp.,
the out-degree) of the vertex corresponding to the monochromatic cell
$C_{i,j}$ in the graph $G$. We apply the following three steps on the
monochromatic cells.

Step 1. We apply this step as long as there exists a cell $C_{i,j}$ with
$d_{in}(C_{i,j})=0$ and $d_{out}(C_{i,j})>0$. For each such cell, we apply the
cell partition procedure on $C_{i,j}$ and remove the out-going edges from
$C_{i,j}$ and from its neighbors $C_{i,j-1}$, $C_{i,j+1}$, $C_{i-1,j}$, and
$C_{i+1,j}$; see Figure 8.

Step 2. We apply this step on the monochromatic cells $C_{i,j}$ with
$d_{in}(C_{i,j})>0$. Consider the grid as an arbitrary white-black chessboard.
For each white cell with $d_{in}(C_{i,j})>0$, we apply the cell partition
procedure on $C_{i,j}$.

Step 3. We apply this step on the empty and the monochromatic cells $C_{i,j}$
with $d_{in}(C_{i,j})=0$ and $d_{out}(C_{i,j})=0$ (that are not considered in
the previous steps). For each such cell, we apply the cell partition procedure
on $C_{i,j}$.

We call a cell $C_{i,j}$ a _partitioned cell_ if $C_{i,j}$ has been
partitioned (using the cell partition procedure), and we call it an _extended
cell_ otherwise. If we have two adjacent partitioned cells $C_{i,j}$ and
$C_{i,j+1}$, then we call the merged area of the two trapezoids
${{\cal{T}}}_{i,j}^{r}$ and ${{\cal{T}}}_{i,j+1}^{l}$ a _lune_ ; see Figure 9.

Figure 9: (a) vertical and (b) horizontal lunes.

At the end of this stage, we have three types of non-empty convex cells:
original $3\times 3$ cells, extended cells, and lunes. Clearly, each original
cell is bichromatic, otherwise, it would have been partitioned or extended in
Steps 1–3. Observe that each extended cell $C_{i,j}$ is bichromatic, since
$d_{in}(C_{i,j})>0$. Observe also that each non-empty lune $L$ is
monochromatic. To see this, assume, w.l.o.g., that $L$ was obtained by
partitioning the cells $C_{i,j}$ and $C_{i,j+1}$ and merging the trapezoids
${{\cal{T}}}_{i,j}^{r}$ and ${{\cal{T}}}_{i,j+1}^{l}$. Thus, $L$ cannot be
bichromatic, since otherwise, there would be a directed edge from $C_{i,j}$ to
$C_{i,j+1}$ and vice versa, which means that one of the cells $C_{i,j}$ and
$C_{i,j+1}$ (the black one in the chessboard) is extended in Step 2.

##### Stage 1.3

In this stage, we get rid of the lunes, by partitioning each lune into sub-
pieces and merging the sub-pieces with adjacent extended cells as follows. Let
$L_{1}$ be a vertical lune obtained by merging two adjacent trapezoids
${{\cal{T}}}_{i,j}^{r}$ and ${{\cal{T}}}_{i,j+1}^{l}$; see Figure 9(a). (A
horizontal lune will be treated analogously.) As observed above, $L_{1}$ is
monochromatic (or empty) which means that the subregion $C_{i,j}^{6}\cup
C_{i,j+1}^{4}\subseteq L_{1}$ is empty of points of $P$.

We consider the four triangles obtained by removing $C_{i,j}^{6}$ from
${{\cal{T}}}_{i,j}^{r}$ and removing $C_{i,j+1}^{4}$ from
${{\cal{T}}}_{i,j+1}^{l}$, and we merge them with the cells $C_{i-1,j}$ ,
$C_{i-1,j+1}$, $C_{i+1,j}$, and $C_{i+1,j+1}$ according to the following
cases. We describe how to merge the top triangles with $C_{i-1,j}$ and
$C_{i-1,j+1}$. (Merging the bottom triangles with $C_{i+1,j}$, and
$C_{i+1,j+1}$ is done analogously.) Let $v_{t}$ be the top vertex of $L_{1}$;
see Figure 10.

  * •

If both $C_{i-1,j}$ and $C_{i-1,j+1}$ are extended cells, then we merge the
top-left triangle with $C_{i-1,j}$ and the top-right triangle with
$C_{i-1,j+1}$; see Figure 10(a).

  * •

If $C_{i-1,j}$ is a partitioned cell and $C_{i-1,j+1}$ is an extended cell,
then we have another horizontal lune $L_{2}$ between $C_{i-1,j}$ and
$C_{i,j}$; see Figure 10(b). Notice that the union of the top-left triangle of
$L_{1}$ and the right-bottom triangle of $L_{2}$ is exactly the sub-cell
$C_{i,j}^{3}$. Notice also that $L_{2}$ is monochromatic and has the same
color as $L_{1}$. Thus, the points of $P$ in $C_{i,j}^{3}$ are of distance 1
from $v_{t}$. In this case, we merge the top-right triangle of $L_{1}$ and the
right-top triangle of $L_{2}$ with $C_{i-1,j+1}$. Moreover, we merge the
region of $C_{i,j}^{3}$ intersecting the disk of radius 1 centered at $v_{t}$
with $C_{i-1,j+1}$; see Figure 10(b).

Figure 10: Merging the top triangles of $L_{1}$ with the cells $C_{i-1,j}$ and
$C_{i-1,j+1}$. The gray and the green regions are part of vertical and
horizontal lunes, respectively, and the light blue regions are empty of points
of $P$.

  * •

If $C_{i-1,j}$ is an extended cell and $C_{i-1,j+1}$ is a partitioned cell,
then this case is symmetric to the previous case; see Figure 10(c).

  * •

If both $C_{i-1,j}$ and $C_{i-1,j+1}$ are partitioned cells, then we have four
lunes incident to $v_{t}$; see Figure 10(d). Since all of the lunes are
monochromatic and have the same color, the triangles of these lunes that are
incident to $v_{t}$ are empty of points of $P$ and, therefore, we remove these
triangles from the division.

Moreover, in each partitioned cell $C_{i,j}$ such that $i=1$, $i=n$, $j=1$, or
$j=n$, we treat the trapezoids adjacent to the boundary of the grid as half-
lunes and we merge them with their adjacent extended cells as in the lunes
case.

Notice that, at the end of this stage, we have two types of non-empty cells:
original $3\times 3$ cells and extended cells, and both types are convex and
bichromatic cells; see Figure 11. From now on, we refer to both types of these
cells as extended cells and denote them by $\hat{C}$. That is, $\hat{C}_{i,j}$
is either an original $3\times 3$ cell $C_{i,j}$ or an extended cell obtained
by merging $C_{i,j}$ with trapezoids from its neighbors.

Figure 11: A subdivision obtained at the end of Stage 1. The light blue
regions are empty of points of $P$.

### Stage 2

In this stage, we construct a planar bichromatic spanning tree in each
(extended) cell and connect them to each other to obtain, overall, a planar
bichromatic spanning tree of $P$. For each cell $\hat{C}_{i,j}$, we denote by
$\hat{P}_{i,j}$ the set of points of $P$ lying in $\hat{C}_{i,j}$. If
$C_{i,j}$ has been partitioned, then we set $\hat{P}_{i,j}=\emptyset$.

##### Stage 2.1

In each cell $\hat{C}_{i,j}$, we construct a planar bichromatic spanning tree
$T_{i,j}$ of $\hat{P}_{i,j}$ as follows. We select an arbitrary red point
$s\in\hat{P}_{i,j}$ as a center of the tree and connect it to each blue point
in the cell to produce a star. We extend the edges of the star to partition
the cell into convex cones, possibly except one cone; see Figure 12. If we
have a non-convex cone, then we divide it into two convex cones by adding its
bisector, as shown in Figure 12(right). Then, we connect all the red points in
each cone to one of the blue points on the lines bounding the cone.

Figure 12: Constructing a planar bichromatic spanning tree in a cell.

######  Lemma 3.1.

Let $T_{i,j}$ be a tree constructed in Stage 2.1 in cell $\hat{C}_{i,j}$ . Any
(red or blue) point $p$ in the plane can be connected to $T_{i,j}$ without
crossing the edges of $T_{i,j}$.

###### Proof.

Let $s$ be the center of $T_{i,j}$ and recall that its color is red. Consider
the cones produced by the rays between $s$ and the blue points of $T_{i,j}$.
Let $C$ be the cone containing $p$ and let $a$ and $b$ be the two blue points
defining $C$. By the way we constructed $T_{i,j}$, all the points in $C$ are
red and connected to exactly one of the points $a$ and $b$, assume, w.l.o.g.,
$a$. We distinguish between two cases with respect to the color of $p$.
Case 1: $p$ is a blue point. If the edge $(s,p)$ does not cross the edges of
$T_{i,j}$, then we connect $p$ to $s$. Otherwise, we connect $p$ to the
endpoint of the first edge (from $p$) crossing $(s,p)$; see Figure 13(a).
Case 2: $p$ is a red point. In this case, we connect $p$ to $a$; see Figure
13(b). ∎

Figure 13: (a) $p$ and $s$ are of different colors. (b) $p$ and $s$ are of the
same color.

##### Stage 2.2

In this stage, we connect between the trees that are constructed in Stage 2.1
to obtain a planar bichromatic spanning tree of $P$. Let $\hat{C}_{i,j}$ and
$\hat{C}_{k,l}$ be two (extended) cells. We say that $\hat{C}_{k,l}$ is a
_side_ adjacent (or s-adjacent for short) cell of $\hat{C}_{i,j}$, if one of
the following holds:

  * •

$k=i+1$ and $l=j$, or

  * •

$k=i$ and $l=j+1$,

and we say that $\hat{C}_{k,l}$ is a _diagonal_ adjacent (or d-adjacent for
short) cell of $\hat{C}_{i,j}$, if one of the following holds:

  * •

$k=i-1$, $l=j+1$, and $C_{i-1,j}$ and $C_{i,j+1}$ have been partitioned, or

  * •

$k=i-1$, $l=j-1$, and $C_{i,j-1}$ and $C_{i-1,j}$ have been partitioned.

We construct a bichromatic spanning tree $T^{\prime}$ of $P$ by traversing the
cells starting from an arbitrary (non-empty) cell (in breadth first search
(BFS) manner). That is, we first initiate a tree $T^{\prime}$ by an arbitrary
tree $T_{i,j}$ that is constructed in a cell $\hat{C}_{i,j}$. Then, we connect
$T^{\prime}$ to all the trees constructed in the cells adjacent to
$\hat{C}_{i,j}$, and proceed from these trees. More precisely, in each step,
we consider a tree $T_{i,j}$, which is already connected to $T^{\prime}$, and
we connect $T^{\prime}$ to all of the trees constructed in the cells adjacent
to $\hat{C}_{i,j}$ via $T_{i,j}$ (if they are not connected yet to
$T^{\prime}$). In the following, we describe how to connect $T^{\prime}$ to
all the trees constructed in the cells adjacent to $\hat{C}_{i,j}$.

Let $\hat{C}$ be a cell adjacent to $\hat{C}_{i,j}$, such that the tree
$T_{C}$ constructed in $\hat{C}$ is not connected yet to $T^{\prime}$. Let
$v_{tr}$, $v_{tl}$, $v_{br}$, and $v_{bl}$ be the top-right, top-left, bottom-
right, and bottom-left vertices of the grid incident to $C_{i,j}$,
respectively; see Figure 14. We distinguish between two cases.
Case 1: $\hat{C}$ is a d-adjacent cell of $\hat{C}_{i,j}$. Assume, w.l.o.g.,
that $\hat{C}=\hat{C}_{i-1,j+1}$. Then, the boundaries of $\hat{C}_{i,j}$ and
$\hat{C}_{i-1,j+1}$ share a common (diagonal) edge $\overline{ab}$; see Figure
14. Moreover, the convex hull of $\hat{C}_{i,j}\cup\hat{C}_{i-1,j+1}$ does not
contain any point of $P\setminus(\hat{P}_{i,j}\cup\hat{P}_{i-1,j+1})$ (this
can be seen clearly in Figure 11). Let $p\in\hat{P}_{i,j}$ be the closest
point to the line passing through $\overline{ab}$, such that no edge of
$T^{\prime}$ crosses the triangle $\Delta pab$. By Claim 3.2, such a point $p$
exists. Then, any edge connecting $p$ to any point of $T_{i-1,j+1}$ does not
cross any non-empty cell except $\hat{C}_{i,j}$ and $\hat{C}_{i-1,j+1}$.
Therefore, by Lemma 3.1, we can connect $p$ to $T_{i-1,j+1}$ without crossing
any other edge of $T^{\prime}$.

Figure 14: Illustration of Case 1. We connect $T_{i-1,j+1}$ to $T_{i,j}$ via
$p$.

Case 2: $\hat{C}$ is an s-adjacent cell of $\hat{C}_{i,j}$. Assume, w.l.o.g.,
that $\hat{C}=\hat{C}_{i,j+1}$. Let $p$ be the rightmost point in
$\hat{P}_{i,j}$, such that no edge of $T^{\prime}$ crosses the triangle
$\Delta pv_{br}v_{tr}$; see Figure 15. By Claim 3.2, such a point $p$ exists.
Let $H$ be the convex hull of $\hat{P}_{i,j+1}\cup\\{p\\}$. We consider two
sub-cases.
Case 2.1: $H\cap(P\setminus(\hat{P}_{i,j}\cup\hat{P}_{i,j+1}))=\emptyset$
(i.e., $H$ does not contain any point of $P$ that is not in
$\hat{P}_{i,j}\cup\hat{P}_{i,j+1}$); see Figure 15. Therefore, by Lemma 3.1,
we can connect $T_{i,j+1}$ to $T_{i,j}$ via $p$, without crossing any other
edge of $T^{\prime}$.

Figure 15: The convex hull $H$ of $\hat{P}_{i,j+1}\cup\\{p\\}$ (consisting of
green segments) does not contain any point of $P$ that is not in
$\hat{P}_{i,j}\cup\hat{P}_{i,j+1}$. We connect $T_{i,j+1}$ to $T_{i,j}$ via
$p$.

Case 2.2: $H\cap(P\setminus(\hat{P}_{i,j}\cup\hat{P}_{i,j+1}))\neq\emptyset$
(i.e., $H$ contains a point of $P$ that is not in
$\hat{P}_{i,j}\cup\hat{P}_{i,j+1}$). In this case, $H$ contains a point in
$\hat{P}_{i-1,j}\cup\hat{P}_{i-1,j+1}$ or in
$\hat{P}_{i+1,j}\cup\hat{P}_{i+1,j+1}$. Assume, w.l.o.g., that $H$ contains a
point in $\hat{P}_{i-1,j}\cup\hat{P}_{i-1,j+1}$; see Figure 16. Notice that
exactly one of the sets $\hat{P}_{i-1,j}$ or $\hat{P}_{i-1,j+1}$ is an empty
set, since, in this case, exactly one of the cells $C_{i-1,j}$ or
$C_{i-1,j+1}$ has been partitioned. We further distinguish between two cases.

  1. 1.

$H\cap\hat{P}_{i-1,j}\neq\emptyset$; see Figure 16(a). In this case we first
connect $T_{i,j+1}$ to $T_{i-1,j}$ as follows. Let $q\in\hat{P}_{i-1,j}$ be
the closest point to the line passing through the boundary edge between
$\hat{C}_{i-1,j}$ and $\hat{C}_{i,j+1}$. Then, the convex hull of
$\hat{P}_{i,j+1}\cup\\{q\\}$ does not contain any point of $P$ that is not in
$\hat{P}_{i,j+1}\cup\\{q\\}$. Therefore, by Lemma 3.1, we can connect
$T_{i,j+1}$ to $T_{i-1,j}$ via $q$, without crossing any other edge of
$T^{\prime}$.

Moreover, if $T_{i-1,j}$ is not connected yet to $T^{\prime}$, then we apply
Case 2 on $\hat{C}_{i-1,j}$ to connect $T_{i-1,j}$ to $T_{i,j}$.

Figure 16: (a) $H$ contains points from $\hat{P}_{i-1,j}$. We connect
$T_{i,j+1}$ to $T_{i-1,j}$ via $q$. (b) $H$ contains a point $z$ from
$\hat{P}_{i-1,j+1}$. We connect $T_{i-1,j+1}$ to $T_{i,j}$ via $q$ and we
connect $T_{i,j+1}$ to $T_{i-1,j+1}$ via $z$.

  2. 2.

$H\cap\hat{P}_{i-1,j+1}\neq\emptyset$. If $T_{i-1,j+1}$ is not connected yet
to $T^{\prime}$, then we first connect $T_{i-1,j+1}$ to $T_{i,j}$ as follows.
Let $q\in\hat{P}_{i,j}$ be the closest point to the line passing through the
boundary edge between $\hat{C}_{i,j}$ and $\hat{C}_{i-1,j+1}$; see Figure
16(b). Then, the convex hull of $\hat{P}_{i-1,j+1}\cup\\{q\\}$ does not
contain any point of $P$ that is not in $\hat{P}_{i-1,j+1}\cup\\{q\\}$.
Therefore, by Lemma 3.1, we can connect $T_{i-1,j+1}$ to $T_{i,j}$ via $q$,
without crossing any other edge of $T^{\prime}$.

Moreover, we connect $T_{i,j+1}$ to $T_{i-1,j+1}$ as follows. Let $a$ be the
bottom-right corner of $C_{i-1,j+1}$. Thus,
$\Delta{pv_{tr}a}\cap\hat{P}_{i-1,j+1}\neq\emptyset$ and
$\Delta{pv_{tr}a}\cap(\hat{P}_{i,j}\setminus\\{p\\})=\emptyset$. Let $z$ be
the bottommost point in $\Delta{pv_{tr}a}\cap\hat{P}_{i-1,j+1}$, such that no
edge of $T^{\prime}$ crosses the triangle $\Delta zv_{tr}a$; see Figure 16(b).
By Claim 3.2, such a point $z$ exists. Then, the convex hull of
$\hat{P}_{i,j+1}\cup\\{z\\}$ does not contain any point of $P$ that is not in
$\hat{P}_{i,j+1}\cup\\{z\\}$. Therefore, by Lemma 3.1, we can connect
$T_{i,j+1}$ to $T_{i-1,j+1}$ via $z$, without crossing any other edge of
$T^{\prime}$. (Notice that the two edges added in this case do not cross each
other.)

#### Correctness Proof

Recall that $T$ is a bichromatic spanning tree of $P$ of minimum bottleneck
$\lambda$. In this section, we prove that $T^{\prime}$ is a planar bichromatic
spanning tree of $P$ of bottleneck at most $8\sqrt{2}\lambda$. Notice that
every point $p\in P$ is contained in a bichromatic cell $\hat{C}_{i,j}$ and
hence, it is connected to $T_{i,j}$, the tree constructed in Stage 2.1 in
$\hat{C}_{i,j}$. Therefore, to show that $T^{\prime}$ is a bichromatic
spanning tree of $P$, it is sufficient to show that each tree $T_{i,j}$ is
connected to $T^{\prime}$.

######  Claim 3.2.

Let $T^{\prime}$ be the tree constructed at some step during Stage 2.2 and
assume that $T^{\prime}$ is planar. Let $T_{i,j}$ be a tree constructed in
$\hat{C}_{i,j}$ and $T_{i,j}$ is already connected to $T^{\prime}$. Let
$\hat{C}$ be an adjacent cell of $\hat{C}_{i,j}$ that shares an edge
$\overline{ab}$ with $\hat{C}_{i,j}$ and let $T_{C}$ be the tree constructed
in $\hat{C}$, and assume that $T_{C}$ is not connected yet to $T^{\prime}$.
Then, there exists a point $p$ in $\hat{C}_{i,j}$, such that no edge of
$T^{\prime}$ crosses the triangle $\Delta pab$.

###### Proof.

Assume, w.l.o.g., that $\hat{C}=\hat{C}_{i,j+1}$, $a=v_{tr}$, and $b=v_{br}$;
see Figure 17. The following procedure shows the existence of such a point
$p$. We sweep leftwards in $\hat{C}_{i,j}$ with a vertical line $l$, starting
from $\overline{v_{tr}v_{br}}$ until we meet a point, or an edge of
$T^{\prime}$. If we first meet a point, then this point satisfies the claim.
Otherwise, we first meet an edge $(p^{\prime},q^{\prime})$ of $T^{\prime}$;
see Figure 17. This could only be when exactly one of the endpoints
$p^{\prime}$ or $q^{\prime}$ is outside $\hat{C}_{i,j}$. Let $C_{l}$ and
$C_{r}$ be the two sub-cells obtained by partitioning $\hat{C}_{i,j}$ with the
line that goes through the points $p^{\prime}$ and $q^{\prime}$. Let $C_{r}$
be the sub-cell containing $v_{tr}$ and $v_{br}$. We keep sweeping leftwards
only inside $C_{r}$. As before, if we first meet a point, then this point
satisfies the claim. Otherwise, we meet an edge
$(p^{\prime\prime},q^{\prime\prime})$ of $T^{\prime}$ before we meet a point.
Then, one of the endpoints $p^{\prime\prime}$ or $q^{\prime\prime}$ is outside
$\hat{C}_{i,j}$. Let $C_{rl}$ and $C_{rr}$ be the two sub-cells obtained by
partitioning $C_{r}$ with the line that goes through the points
$p^{\prime\prime}$ and $q^{\prime\prime}$. Let $C_{rr}$ be the sub-cell
containing $v_{tr}$ and $v_{br}$. We keep sweeping leftwards only inside
$C_{rr}$, until we meet a point, and this point satisfies the claim. Notice
that, in the last sweep we meet a point before we meet an edge of
$T^{\prime}$. This follows from the planarity of $T^{\prime}$. ∎

Figure 17: Illustration of the proof of Claim 3.2.

######  Lemma 3.3.

Let $T_{i,j}$ be a tree constructed in $\hat{C}_{i,j}$ in Stage 2.1 and assume
that $T_{i,j}$ is already connected to $T^{\prime}$. Then, at the end of Stage
2.2, all the trees that are constructed in the cells adjacent to
$\hat{C}_{i,j}$ are connected to $T^{\prime}$ as well.

###### Proof.

Let $\hat{C}$ be an adjacent cell of $\hat{C}_{i,j}$. We distinguish between
two cases.
Case 1: $\hat{C}$ is a d-adjacent cell of $\hat{C}_{i,j}$. Assume, w.l.o.g.,
that $\hat{C}=\hat{C}_{i-1,j+1}$. Then, in Stage 2.2, Case 1, we connect
between $T_{i,j}$ and $T_{i-1,j+1}$.
Case 2: $\hat{C}$ is an s-adjacent cell of $\hat{C}_{i,j}$. Assume, w.l.o.g.,
that $\hat{C}=\hat{C}_{i,j+1}$. As described in Stage 2.2, we select a point
$p\in\hat{C}_{i,j}$ and compute the convex hull $H$ of
$\\{p\\}\cup\hat{P}_{i,j+1}$. Then, we consider two cases. In Case 2.1, when
$H$ does not contain any point of
$P\setminus(\hat{P}_{i,j}\cup\hat{P}_{i,j+1})$, we connect $T_{i,j}$ directly
to $T_{i,j+1}$ (via $p$). And, in Case 2.2, when $H$ contains a point of
$P\setminus(\hat{P}_{i,j}\cup\hat{P}_{i,j+1})$, we connect $T_{i,j+1}$ to
$T_{i,j}$ via the tree $T_{i-1,j+1}$, in case that $H$ contains a point of
$\hat{P}_{i-1,j+1}$ (or via the tree $T_{i+1,j+1}$, in case that $H$ contains
a point of $\hat{P}_{i+1,j+1}$).
In the case that $H$ contains a point of $\hat{P}_{i-1,j}$ (symmetrically, $H$
contains a point of $\hat{P}_{i+1,j}$), we connect $T_{i,j+1}$ to $T_{i,j}$
via the tree $T_{i-1,j}$. If $T_{i-1,j}$ is already connected to $T_{i,j}$,
then we are done. Otherwise, since $\hat{C}_{i-1,j}$ is an s-adjacent cell of
$\hat{C}_{i,j}$, we will try to connect $T_{i-1,j}$ to $T_{i,j}$ in the next
iteration in Stage 2.2 (by applying Case 2 once again). In the next iteration,
either we connect $T_{i-1,j}$ to $T_{i,j}$ in one of the cases described above
or we end up by connecting $T_{i,j-1}$ to $T_{i-1,j}$. In the latter case, if
$T_{i,j-1}$ is already connected to $T_{i,j}$, then we are done. otherwise,
$T_{i+1,j}$ is already connected to $T_{i,j}$. In this case, we connect
$T_{i,j-1}$ to $T_{i,j}$ either directly or via $T_{i+1,j}$, and we are done.
∎

######  Lemma 3.4.

Let $p$ and $q$ be two points of $P$, such that $p$ and $q$ are of different
colors, $|pq|\leq\lambda$ and $p$ belongs to $T^{\prime}$. Then, $q$ also
belongs to $T^{\prime}$.

###### Proof.

Since $|pq|\leq\lambda$, either $p$ and $q$ are in the same cell or they are
in adjacent cells. If they are in the same cell $\hat{C}_{i,j}$, then, after
Stage 2.1, they are connected in $T_{i,j}$, and the lemma holds. Otherwise,
assume, w.l.o.g., that $p\in\hat{C}_{i,j}$ and $q\in\hat{C}$, where $\hat{C}$
is adjacent to $\hat{C}_{i,j}$. Then, after Stage 2.1, $p$ belongs to
$T_{i,j}$ and $q$ belongs to $T_{C}$, the tree constructed in $\hat{C}$. Since
$T_{i,j}$ is part of $T^{\prime}$ and $\hat{C}$ is adjacent to
$\hat{C}_{i,j}$, by Lemma 3.3, $T_{i,j}$ is connected to $T_{C}$ and therefore
$q$ belongs to $T^{\prime}$. ∎

######  Lemma 3.5.

Let $T_{i,j}$ be a tree constructed in $\hat{C}_{i,j}$. Then, $T_{i,j}$ is
connected to $T^{\prime}$.

###### Proof.

Assume by contradiction that $T_{i,j}$ is not connected to $T^{\prime}$. Let
$a$ be a point from $T^{\prime}$ and let $b$ be a point from $T_{i,j}$. Since
$T$ is a bottleneck bichromatic spanning tree of $P$, there is a path $\Pi$
between $a$ and $b$ in $T$. Let $p$ be the last point (from $a$) on $\Pi$ that
belongs to $T^{\prime}$, i.e., no point of $T^{\prime}$ appears on the sub-
path of $\Pi$ between $p$ and $b$. Since $b$ does not belong to $T^{\prime}$,
such a point $p$ exists. Let $q$ be the point between $p$ and $b$ on $\Pi$
that is connected to $p$. By the selection of $p$, $q$ does not belong to
$T^{\prime}$. Since the bottleneck of $T$ is $\lambda$, we have
$|pq|\leq\lambda$. Therefore, by Lemma 3.4, $p$ and $q$ are connected in
$T^{\prime}$, which contradicts that $q$ does not belong to $T^{\prime}$. ∎

######  Lemma 3.6.

$T^{\prime}$ is planar.

###### Proof.

Each $T_{i,j}$ is planar. We start with $T^{\prime}=T_{i,j}$, where $T_{i,j}$
is an arbitrary tree constructed in $\hat{C}_{i,j}$, and in each step, we
extend $T^{\prime}$ by connecting it to the trees corresponding to the cells
adjacent to the current cell. We connect $T^{\prime}$ to a “new” tree
$T_{i,j}$ by picking a point $p$ in $T^{\prime}$, such that the convex hull
$H$ of $\\{p\\}\cup\hat{P}_{i,j}$ is empty of any other points and no edge of
$T^{\prime}$ crosses $H$. In Claim 3.2, we showed that such a point $p$ always
exists. Thus, connecting $p$ to any point of $T_{i,j}$ will not cross any
other edge of $T^{\prime}$ nor of any other tree. Moreover, in Lemma 3.1, we
show that we can always connect $p$ to $T_{i,j}$ without crossing any of the
edges of $T_{i,j}$. Therefore, connecting $T^{\prime}$ to $T_{i,j}$ does not
produce any crossing. ∎

######  Lemma 3.7.

The bottleneck of $T^{\prime}$ is at most $8\sqrt{2}\lambda$.

###### Proof.

Consider Figure 11. After Stage 1, each extended cell is contained in a square
of size $5\lambda\times 5\lambda$, and hence the bottleneck of each tree
constructed in Stage 2.1 is at most $5\sqrt{2}\lambda$. Moreover, every two
d-adjacent cells are contained in a square of size $8\lambda\times 8\lambda$
and every two s-adjacent cells are contained in a square of size
$8\lambda\times 5\lambda$. Thus, each edge added in Stage 2.2 is of length at
most $8\sqrt{2}\lambda$. Therefore, each edge in $T^{\prime}$ is of length at
most $8\sqrt{2}\lambda$. ∎

The algorithm consists of two main stages, and each one of them can be
implemented in polynomial time. Therefore, the total running time of the
algorithm is polynomial. The following theorem summarizes the result of this
section.

######  Theorem 3.8.

Let $P$ be a set of $n$ red and blue points in the plane. One can compute in
polynomial time a planar bichromatic spanning tree of $P$ of bottleneck at
most $8\sqrt{2}$ times the bottleneck of an optimal bichromatic spanning tree
of $P$.

## References

  * [1] M. Abellanas, J. Garcia-Lopez, G. Hernández-Peñalver, M. Noy, and P. A. Ramos.  Bipartite embeddings of trees in the plane.  Discr. Appl. Math., 93(2-3):141–148, 1999.
  * [2] A. K. Abu-Affash, A. Biniaz, P. Carmi, A. Maheshwari, and M. Smid.  Approximating the bottleneck plane perfect matching of a point set.  Comput. Geom., 48(9):718–731, 2015.
  * [3] A. K. Abu-Affash, P. Carmi, M. J. Katz, and Y. Trabelsi.  Bottleneck non-crossing matching in the plane.  Comput. Geom., 47(3):447–457, 2014.
  * [4] P. K. Agarwal.  Partitioning arrangements of lines II: Applications.  Discr. Comput. Geom., 5(1):533–573, 1990.
  * [5] P. K. Agarwal, H. Edelsbrunner, and O. Schwarzkopf.  Euclidean minimum spanning trees and bichromatic closest pairs.  Discr. Comput. Geom., 6(1):407–422, 1991.
  * [6] O. Aichholzer, S. Cabello, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, and D. R. Wood.  Edge-removal and non-crossing configurations in geometric graphs.  In EuroCG, pages 119–122, 2008.
  * [7] N. Alon, S. Rajagopalan, and S. Suri.  Long non-crossing configurations in the plane.  In SoCG, pages 257–263, 1993.
  * [8] G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu, R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara, and P. Taslakian.  Matching points with things.  In LATIN, volume 6034 of LNCS, pages 456–467, 2010.
  * [9] S. Arora and K. L. Chang.  Approximation schemes for degree-restricted MST and red–blue separation problems.  Algorithmica, 40(3):189–210, 2004.
  * [10] M. J. Atallah and D. Z. Chen.  On connecting red and blue rectilinear polygonal obstacles with nonintersecting monotone rectilinear paths.  Int. J. Comput. Geom. Appl., 11(4):373–400, 2001.
  * [11] A. Biniaz, P. Bose, K. Crosbie, J.-L. De Carufel, D. Eppstein, A. Maheshwari, and M. H. M. Smid.  Maximum plane trees in multipartite geometric graphs.  Algorithmica, 81(4):1512–1534, 2019.
  * [12] A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. H. M. Smid.  Spanning trees in multipartite geometric graphs.  Algorithmica, 80(11):3177–3191, 2018.
  * [13] A. Biniaz, A. Maheshwari, and M. Smid.  Bottleneck bichromatic plane matching of points.  In CCCG, 2014.
  * [14] J.-D. Boissonnat, J. Czyzowicz, O. Devillers, J. Urrutia, and M. Yvinec.  Computing largest circles separating two sets of segments.  Int. J. Comput. Geom. Appl., 10(1):41–53, 2000.
  * [15] M. G. Borgelt, M. Van Kreveld, M. Löffler, J. Luo, D. Merrick, R. I. Silveira, and M. Vahedi.  Planar bichromatic minimum spanning trees.  J. Discrete Algorithms, 7(4):469–478, 2009.
  * [16] E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, H. Meijer, M. H. Overmars, and S. Whitesides.  Separating point sets in polygonal environments.  Int. J. Comput. Geom. Appl., 15(4):403–420.
  * [17] A. Dumitrescu and R. Kaye.  Matching colored points in the plane: some new results.  Comput. Geom., 19(1):69–85, 2001.
  * [18] A. Dumitrescu and J. Pach.  Partitioning colored point sets into monochromatic parts.  Int. J. Comput. Geom. Appl., 12(05):401–412, 2002.
  * [19] H. Everett, J.-M. Robert, and M. J. van Kreveld.  An optimal algorithm for the (<= k)-levels, with applications to separation and transversal problems.  Int. J. Comput. Geom. Appl., 6(3):247–261, 1996.
  * [20] A. Kaneko and M. Kano.  Discrete geometry on red and blue points in the plane – a survey.  Discr. Comput. Geom., 25:551–570, 2003.
  * [21] D. Lichtenstein.  Planar formulae and their uses.  SIAM J. Comput., 11(2):329–343, 1982.
  * [22] H. G. Mairson and J. Stolfi.  Reporting and counting intersections between two sets of line segments.  In Theoretical Foundations of Computer Graphics and CAD, volume 40 of NATO ASI Series, pages 307–325, 1988.