#  SceneReplica: Benchmarking Real-World Robot Manipulation by Creating
Reproducible Scenes

Ninad Khargonkar* Sai Haneesh Allu* Yangxiao Lu Jishnu Jaykumar P
Balakrishnan Prabhakaran Yu Xiang
The University of Texas at Dallas
<EMAIL_ADDRESS>*equal contribution

###### Abstract

We present a new reproducible benchmark for evaluating robot manipulation in
the real world, specifically focusing on pick-and-place. Our benchmark uses
the YCB objects, a commonly used dataset in the robotics community, to ensure
that our results are comparable to other studies. Additionally, the benchmark
is designed to be easily reproducible in the real world, making it accessible
to researchers and practitioners. We also provide our experimental results and
analyzes for model-based and model-free 6D robotic grasping on the benchmark,
where representative algorithms are evaluated for object perception, grasping
planning, and motion planning. We believe that our benchmark will be a
valuable tool for advancing the field of robot manipulation. By providing a
standardized evaluation framework, researchers can more easily compare
different techniques and algorithms, leading to faster progress in developing
robot manipulation methods. 111Project page is available at
https://irvlutd.github.io/SceneReplica

> Keywords: Robot Manipulation, Benchmarking, Real World Scene Replication

##  1 Introduction

Benchmarking has been crucial for successfully boosting the rate of research
in machine learning-related communities. With a common benchmark for
experiments, different algorithms can be compared in a fair and standardized
manner, and a relative improvement between them can be established. Perhaps
the most well-known benchmark in AI research is the ImageNet dataset [1] and
its associated challenge [2]. It has been used to train and test image
classification methods and can be attributed to triggering the network
architecture revolution in deep learning. The KITTI dataset [3] has been
widely used to study problems related to autonomous driving such as car
detection and tracking, lane segmentation, and odometry estimation. In NLP, a
wide variety of benchmarks were introduced with different levels of
difficulty, such as GLUE [4], SuperGLUE [5] and MMLU [6]. In robotics,
researchers have proposed several benchmarks for different tasks, such as the
NIST assembly boards [7] for assembly and the GRASPA [8] for grasping.
However, most of them have not seen widespread adoption and usage, thereby
limiting the rate of research progress as it becomes harder to compare methods
and investigate their true applicability on a problem.

The main difficulty in benchmarking in robotics is that robots need to perform
tasks in the real world involving a complex pipeline instead of running
experiments on fixed datasets. Fixed datasets have the advantage that every
algorithm can be evaluated on the same data for a fair comparison. Real-world
tasks are hampered by this requirement of a common test dataset, and it is
difficult to make sure that the test scenarios are exactly the same across
different research labs. Despite this, the robotics community has made
progress along several interesting directions for benchmarking, especially
robot manipulation. First, for assembly tasks, the NIST assembly boards [7]
can be used as a reproducible test bed. Second, the YCB Object and Model Set
[9] provides a set of objects with their 3D mesh models that are accessible to
all researchers. Although these objects are limited to dozens of rigid
objects, using these objects for manipulation provides the same accessible
test objects for experiments. Third, several benchmarking protocols for real-
world manipulation are introduced using YCB objects. These protocols show how
to arrange objects in the real world to create reproducible scenes. For
example, [10] introduces a grasp planning protocol that uses drawing on the
robot workspace for the placement of objects. GRASPA [8] uses printable boards
with AR tags for reproducible placement of YCB objects. However, [10] cannot
guarantee accurate reproducible object placement, while [8] has to use AR tags
which create unnatural scenes for testing.

In this work, we introduce a new benchmark, SceneReplica, for real-world robot
manipulation to overcome the limitations of existing benchmarks. First, we use
16 YCB objects which can be easily purchased either online (online purchase
links provided) or in person. Second, we created a dataset of 20 scenes with 5
YCB objects in each scene as a test bed for pick-and-place. We introduce a
sequential algorithm for scene generation and selection in simulation to
create these 20 scenes. The algorithm considers the reachability space of a
robot and the diversity of poses of objects in building the real-world test
bed. Finally, we provide an easy-to-use tool to guide users in reproducing
these 20 scenes in the real world without using any AR tag or external
equipment. To the best of our knowledge, SceneReplica is the only benchmark
for real-world reproducible scenes without using AR markers or external
cutouts to guide object placement.

Another contribution of our work is the benchmarking of two main paradigms for
6D robotic grasping using SceneReplica: model-based grasping and model-free
grasping. Model-based grasping leverages 3D models of objects for perception
and planning. It consists of a pipeline of using 6D object pose estimation for
perception [11, 12, 13], 3D model-based grasp planning [14, 15] and motion
planning and motion control [16] to reach the planned grasps. Model-free
grasping does not assume the availability of 3D object models. It consists of
a pipeline of unseen object instance segmentation [17, 18, 19], object point
cloud-based grasp planning [20, 21] and motion planning and motion control
[16] to reach the planned grasps. Different object perception, grasping
planning, motion planning, and control methods can be evaluated within the two
6D robotic grasping paradigms. This high-level view of robot manipulation
benchmarking is a departure from existing benchmarks which are specific to
some tasks or do not give details about the complete pipeline. We also perform
experiments and provide our analyses on a selected set of representative
methods. To the best of our knowledge, it is the first effort in which model-
based and model-free grasping pipelines are systematically evaluated and
fairly compared to each other using the same real-world testing scenes.

By creating SceneReplica, we provide the robotics community with an easy-to-
setup, reproducible real-world benchmark for robot manipulation tasks. We plan
to continuously maintain the benchmark and evaluate additional and upcoming
perception, planning, and control methods on it. It is our hope that these
results, which combine effects from the entire pipeline, can serve as a
reference for robot manipulation research.

Benchmark Type Task Objects AR Tag-Free Scene Reproducibility Meta-World [22]
Simulation 50 tasks Synthetic ✓ ✓ RLBench [23] Simulation 100 Tasks Synthetic
✓ ✓ robosuite [24] Simulation 9 Tasks Synthetic ✓ ✓ Grasp Planning Protocol
[10] Real Grasp Planning YCB (single) ✓ ✗ NIST Assembly [7] Real Assembly Task
Boards ✓ ✓ FurnitureBench [25] Real Assembly 3D Printing ✗ ✓ GRASPA [8] Real
Grasping YCB (clutter) ✗ ✓ OCRTOC [26] Real Rearrangement YCB + Others ✓ ✗ RB2
[27] Real Pouring, Scooping Others ✓ ✗ Zipping, Insertion Box and Blocks Test
[28] Real Pick-and-Place Blocks ✓ ✗ SceneReplica (Ours) Real Pick-and-Place
YCB (clutter) ✓ ✓

Table 1: Comparison between different robotic manipulation benchmarks.

##  2 Related Work

Simulation-based Robotic Benchmarks. Since reproducibility in the real world
is challenging, the setup of testing environments in physics simulators
provides a workaround for benchmarking in robotics. For example, the Meta-
World [22] benchmark introduces 50 robotic manipulation tasks, which can be
used to study meta-reinforcement learning and multitask learning. The
robosuite [24] based on the MuJoCo physics engine [29] supports 9 manipulation
tasks for different robots. The RLBench benchmark [23] increases the number of
tasks to 100. The advantage of using simulation is that reproducibility is
guaranteed for evaluation, and a large number of tasks can be used. However,
due to the sim-to-real gap, the performance in simulation cannot simply be
transferred to the real world. Although we can work on improving the physics
simulators, nuances in the real world such as lighting, friction, external
perturbation, etc., are extremely difficult to model in simulation. We need to
have real-world benchmarks for robotics.

Real-world Robotic Benchmarks. We summarize a list of representative efforts
to benchmark robot manipulation in the real world in Table 1. According to the
evaluation tasks, they can be classified into assembly [7, 25], grasping [10,
28, 8], rearrangement [26], and others (pouring, scooping zipping, insertion
in [27]). In terms of scene reproducibility in evaluation, NIST Assembly [7],
FurnitureBench [25] and GRASPA [8] are the only three benchmarks whose test
scenes are reproducible. NIST Assembly uses a fixed set of assembly task
boards, while FurnitureBench and GRASPA use AR markers to guide the scene
creation process. For grapsing and picking-and-place, SceneReplica is the only
benchmark that can create reproducible scenes without using AR markers in the
real world.

##  3 The SceneReplica Benchmark

Our goal is to introduce reproducible scenes of objects for robot
manipulation, where researchers can set up the same set of scenes in different
environments for evaluation. Currently, we focus on tabletop cluttered scenes
for pick-and-place. The configurations of objects in these scenes are
generated in the Gazebo simulation environment to obtain the ground truth data
and in order to make it easy to satisfy certain properties of the scenes.
Generating in simulation enables access to complete state information,
allowing for a seamless sim2real transfer for reproducible real-world
experiments.

###  3.1 Creating Scenes in Simulation

Figure 1: 16 YCB objects are used in SceneReplica.

Object Set. 16 YCB objects [9] are used in our benchmark to create scenes.
Their 3D mesh models are shown in Fig. 1. We select these objects because i)
they can be easily purchased online or in grocery stores; ii) they are a
subset of the YCB Video dataset [11] which has been widely used to study 6D
object pose estimation. Therefore, we can leverage existing 6D object pose
estimation methods for experiments, for example, [11, 13].

Stable Poses of Objects. To place objects on a table in Gazebo, one option is
to drop them from a certain height above the table and then let the physics
simulator handle the computation for the final position of the objects.
However, we found that this process requires careful parameter tuning of the
mass and inertia of objects, and waiting for the objects to settle down is
slow in practice. Therefore, we opt to compute stable poses of objects which
are object orientations when they rest statically on a planar surface. Such
stable poses are also safe to use in real world scenes as the chance of an
object falling over and disturbing the scene is low. We used the
compute_stable_poses() function in trimesh [30] to obtain such poses, and Fig.
1 shows examples of stable poses of some YCB objects.

Determining the Reachable Space of a Robot. When placing these objects on a
table for manipulation, we need to place them within the reach of the robot.
We employ a simple algorithm as depicted in Fig. 2 to compute the reachable
regions of a tabletop. In Step I, the robot model is loaded in Gazebo and
maneuvered to the stow position. Next, a table of dimension $1m$ x $1m$ x
$0.745m$ is placed at an offset of $(0.8,0,0)$ with respect to the robot
model, where the $x$-axis is the forward direction of the robot. In Step II,
the surface of the table is partitioned into grids $16\times 16$ and a block
of size $3cm\times 3cm$ is placed in the center of each cell of the grid. In
Step III, we determine whether there is a feasible motion plan for the stand-
off pose $S_{di}$ for each cube i. Blocks that do not have a feasible plan
will be removed from the scene. Steps II - III are run for 20 iterations.
Finally, the remaining blocks after the iterative process indicate discretized
reachable locations for the robot. These locations will be used to place YCB
objects to create scenes.

Figure 2: For a tabletop scene, we use motion planning to see if a Fetch robot
can pick up these blue blocks on the table to determine the reachability of
the robot. After planning, the remaining blocks on the table indicate
reachable points of the tabletop.

Scene Generation. Using the stable poses of the 16 YCB objects, we can
generate random scenes in Gazebo by placing them in the reachable locations of
the Fetch robot. We limit the maximum number of objects in a scene to be five
and sequentially add objects to the scene one by one. Initially, an object is
placed randomly on the table. When adding the next object, we randomly sample
a nearby reachable location with an existing object that is collision-free
between these objects. Stable poses of objects are also randomly sampled
during placement. This process repeats until five objects are added to the
scene. By sampling nearby reachable locations, we tend to generate cluttered
scenes where objects occlude each other. In total, we have generated 164
scenes as candidates for scene selection as described below.

Figure 3: 20 scenes in our SceneReplica benchmark with 5 YCB objects in each
scene.

Scene Selection. After generating a set of scenes, our remaining task is to
select a subset of it as the final scenes for evaluation. We target at
selecting 20 scenes and wish to have the following properties of the selected
scenes. i) The number of appearances of each object should be balanced in the
selected scenes. We define a range $[C_{\text{min}},C_{\text{max}}]$ such that
the counter of each object should be in this range. ii) The selected scenes
should cover the stable poses of each object as much as possible. iii) All the
objects in a selected scene should be reachable from the robot. To check the
reachability of objects in a scene, we use GraspIt! to generate 100 grasps of
each YCB object, and check if there is a motion plan of the Fetch robot to
reach one of the planned grasps.

With these three properties, our algorithm for scene selection works as
follows. We generate a large number of scene sets. Each scene set contains 20
scenes, and it satisfies properties i) and iii). In addition, each set of
scenes is given a score on how many stable poses of these 16 YCB objects are
covered by the 20 scenes in it. This acts as a measure for the diversity of a
set. Finally, we select the scene set with the highest pose coverage score.
Fig. 3 shows the final 20 scenes selected for SceneReplica.

Figure 4: The process of replicating a scene in the real world. The image of
the reference scene is overlaid on the image of the real camera to guide how
to place objects into the real-world scene.

###  3.2 Reproducing Scenes in the Real World

Figure 5: Illustration of the coordinate frames.

To use the 20 selected scenes for experiments, we need to replicate these
scenes in the real world. Previous benchmarks rely on AR markers to create
reproducible scenes [8, 25]. In contrast, we show that directly using the
scene images in Fig. 3 as reference images, we can place objects in the real
world as in the simulator. The process of replicating a scene in the real
world is illustrated in Fig. 4. First, the Fetch camera pose in the real world
is set to be the same as in the simulation. Therefore, the camera extrinsics,
that is, the SE(3) transformation from the robot base frame to the RGB camera
frame, is always the same. This can be done by controlling the Fetch head
pose. Second, the table height in the real world should be the same as in the
simulation, i.e., $0.745m$. We assume that researchers can use a height-
adjustable table for experiments. Third, with the same camera extrinsics and
table height, we can overlay the half-transparent version of an RGB image of a
reference scene to the real RGB image from the Fetch camera, which visually
tells a user how to place these YCB objects. Finally, the user can place
objects by interactively checking the overlap between the reference image and
the real-world image for accurate alignment (Fig. 4). This process makes sure
that the poses of objects in the camera frame are replicated according to the
reference image. Since camera extrinsics are the same in simulation and in the
real world, object poses in the robot base frame are replicated for
manipulation. Fig. 5 illustrates these coordinate frames.

##  4 Model-based and Model-free 6D Grasping

The manipulation task we benchmark with SceneReplica is tabletop pick-and-
place. A robot needs to pick up objects and place them on a fixed location on
the table. The task requires 6D grasping, where the 3D orientation and 3D
translation of a robot gripper is controlled, in contrast to top-down
grasping. In the literature, 6D grasping approaches can be classified into
model-based ones (Fig. 6) and model-free ones (Fig. 7), depending on the
availability of 3D object models.

###  4.1 Model-based 6D Grasping

Figure 6: Model-based grasping pipeline used for benchmarking

Model-based Object Perception. When 3D models of objects are available, we can
tackle the _6D object pose estimation_ problem for object perception. The goal
is to estimate the 3D orientation and 3D translation of the object with
respect to the camera frame. 6D object pose estimation is an active research
area in both robotics and computer vision [31]. When considering the problem
as a pure perception problem, we can evaluate the accuracy of pose estimation
on existing datasets. However, it is unclear how the accuracy of the pose
estimation affects grasping. In SceneReplica, we combine 6D object pose
estimation methods with planning and control for 6D grasping. Consequently, we
can analyze the effect of object pose estimation accuracy on the grasping
success rate.

Model-based Grasp Planning. Model-based grasp planning methods such as
GraspIt! [14] and OpenRAVE [15] use 3D models of objects in physics simulators
to generate grasps. We use GraspIt! in our experiments. We initially generated
a large number of grasps from GraspIt! for each YCB object and later sampled
the initial set to generate a fixed amount of grasps using the farthest point
sampling algorithm which ensures diversity of gripper position with respect to
the object.

Model-based Motion Planning. Once the 6D pose of a target object is estimated,
we can transform the planned grasps on the 3D object model to the robot base
frame. Then we simply loop over each grasp and use a motion planning algorithm
such as algorithms in the open motion planning library (OMPL) [16] to see if
there is a trajectory to reach the grasp. Once a trajectory is returned, we
break the loop and execute the trajectory to grasp the target. Since poses of
all the objects in the scene can be estimated, we can use the 3D models of
objects as obstacles in the planning scene.

###  4.2 Model-free 6D Grasping

Figure 7: Model-free grasping pipeline used for benchmarking

Model-free Object Perception. When is no 3D model of objects available, we can
tackle the _unseen object instance segmentation (UOIS)_ problem [17, 18, 19]
to segment arbitrary objects. Once the objects are segmented, model-free grasp
planning methods can be used to generate grasps of the segmented objects. UOIS
methods are usually trained using synthetic images of a large number of
objects. They learn the concepts of objects and are able to segment novel
objects in the real world.

Model-free Grasp Planning. Grasp planning methods such as 6D GraspNet [20, 21]
take point clouds of objects or whole scenes as input and output grasps of
objects in the scenes. These methods are based on trained neural networks for
grasp synthesis. Similarly to unseen object instance segmentation in
perception, they are trained with large numbers of objects with their
corresponding grasps. Therefore, they can be applied for grasp planning of
novel objects using partial point clouds.

Model-free Motion Planning. Once a target object is segmented and grasps of
the target object are synthesized, similar to model-based motion planning, we
can utilize a motion planning algorithm to generate a trajectory to reach one
of the planned grasps. The main difference between model-based motion planning
is that we do not have 3D models of objects to set up the planning scene for
obstacle avoidance. Therefore, we simply compute an oriented 3D bounding box
for each segmented object for obstacle avoidance during motion planning.

##  5 Experiments

For pick-and-place tasks, the most important evaluation metric is the success
rate of transporting objects from one location to another. The success rate
depends on all the components of a framework. For example, no matter how good
the perception is, if grasp planning of an object has error, the robot would
not be able to pick up the object. Therefore, we evaluated the success rate of
pick-and-place of the 100 objects in SceneReplica, that is, 20 scenes $\times$
5 objects per scene. In addition, we provide perception evaluation and failure
analysis of the results.

Perception Metrics. We consider two perception problems in SceneReplica: 6D
object pose estimation for model-based grasping and unseen object instance
segmentation for model-free grasping. We follow the standard evaluation
metrics for these two problems. We use the average distance for symmetric
objects (ADD-S) metric as in [11] for pose estimation. For unseen object
instance segmentation, we follow [17, 18] to compute precision, recall,
F-measure for region overlap and boundary overlap, as well as the percentage
of segmented objects with Overlap F-measure $\geq 75\%$.

Type | Phase | Description
---|---|---
Perception failure | Pre-Grasping | Target object is not recognized, for example, no pose estimation or no segmentation mask
Perception failure | Pre-Grasping | Grasp not found, perception error of obstacle $>$ threshold
Perception failure | During-Grasping | Grasp planned, failed to grasp and lift, perception error of target $>$ threshold
Perception failure | During-Grasping | Grasp planned, hit obstacle, perception error of obstacle $>$ threshold
Planning failure | Pre-Grasping | No perception failure, but no plan found to grasp target
Planning failure | During-Grasping | Grasp planned, no perception failure, failed to grasp and lift or hit obstacle
Execution failure | Post-Grasping | Failed to place object after grasping and lifting

Table 2: Different types of failures in our pick-and-place experimental
analysis.

Pick-and-place Failure Analysis. When a pick-and-place failure occurred, the
failure can be classified into several different categories: (1) perception
failure (PEF), (2) planning failure (PLF) and (3) execution failure (EF).
Table 2 describes these failures in detail.

Method # | Perception | Grasp Planning | Motion Planning | Control | Ordering | Pick-and-Place Success | Grasping Success
---|---|---|---|---|---|---|---
Model-based Grasping |
1 | PoseRBPF [13] | GraspIt! [14] \+ Top-down | OMPL [16] | MoveIt | Near-to-far | 58 / 100 | 64 / 100
1 | PoseRBPF [13] | GraspIt! [14] \+ Top-down | OMPL [16] | MoveIt | Fixed | 59 / 100 | 59 / 100
2 | PoseCNN [11] | GraspIt! [14] \+ Top-down | OMPL [16] | MoveIt | Near-to-far | 48 / 100 | 50 / 100
2 | PoseCNN [11] | GraspIt! [14] \+ Top-down | OMPL [16] | MoveIt | Fixed | 38 / 100 | 44 / 100
Model-free Grasping |
3 | UCN [18] | GraspNet [20] \+ Top-down | OMPL [16] | MoveIt | Near-to-far | 43 / 100 | 46 / 100
3 | UCN [18] | GraspNet [20] \+ Top-down | OMPL [16] | MoveIt | Fixed | 39 / 100 | 42 / 100
4 | UCN [18] | Contact-graspnet [21] \+ Top-down | OMPL [16] | MoveIt | Near-to-far | 60 / 100 | 63 / 100
4 | UCN [18] | Contact-graspnet [21] \+ Top-down | OMPL [16] | MoveIt | Fixed | 60 / 100 | 64 / 100
5 | MSMFormer [19] | GraspNet [20] \+ Top-down | OMPL [16] | MoveIt | Near-to-far | 38 / 100 | 41 / 100
5 | MSMFormer [19] | GraspNet [20] \+ Top-down | OMPL [16] | MoveIt | Fixed | 36 / 100 | 41 / 100
6 | MSMFormer [19] | Contact-graspnet [21] \+ Top-down | OMPL [16] | MoveIt | Near-to-far | 57 / 100 | 65 / 100
6 | MSMFormer [19] | Contact-graspnet [21] \+ Top-down | OMPL [16] | MoveIt | Fixed | 61 / 100 | 70 / 100

Table 3: Six frameworks of model-based and model-free grasping evaluated on
SceneReplica.

Pose Method | ADD-S | Segmentation Method | Overlap | Boundary |
---|---|---|---|---|---
P | R | F | P | R | F | %75
PoseCNN [11] | 66.01 | UCN+ [18] | 70.0 | 81.2 | 71.9 | 48.3 | 57.2 | 50.3 | 77.6
PoseRBPF [13] | 68.73 | MSMFormer+ [19] | 76.1 | 83.3 | 76.3 | 56.0 | 61.4 | 57.0 | 80.2

Table 4: Perception evaluation of pose estimation and unseen object instance
segmentation in the real world.

###  5.1 Benchmarking Results

Table 3 shows the six different grasping frameworks that we have benchmarked.

Grasping Orders. For grasping in cluttered scenes, the order of grasping
objects matters. We evaluate two orders in SceneReplica: the near-to-far order
based on object perception and the fixed order we defined for each scene.
Intuitively, the near-to-far order is simpler, since the robot can clear up
closer objects first, which are occluders of other objects.

Model-based Grasping Frameworks. For model-based grasping, we have evaluated
two 6D object pose estimation methods: PoseCNN [11] and PoseRBPF [13].
GraspIt! [14] is used for grasp planning in model-based grasping. The OMPL
library [16] in MoveIt is used to plan the trajectory of the robot arm and
control to follow the planned trajectory. In cases when there is no motion
plan to reach all the grasps from GraspIt!, we simply apply top-down grasping
to grasp the target object.

From Table 3 we can see that the PoseRBPF-based framework achieves a higher
success rate in both grasping and pick-and-place compared to the PoseCNN-based
framework. PoseRBPF is a pose-tracking-based estimation method that can
leverage temporal information to stabilize pose estimation compared to
PoseCNN. The accuracy of pose estimation in terms of ADD-S is presented in
Table 4, which is calculated using 200 images in the real world, that is, 20
scenes $\times$ 5 grasps per scene $\times$ 2 orders. A better pose estimation
model improves the success rate.

Model-free Grasping Frameworks. We have evaluated two unseen object
segmentation methods: UCN [18] and MSMFormer [19], two grasp planning methods:
6D GraspNet [20] and Contact-GraspNet [21]. The OMPL library [16] in MoveIt
used for motion planning and control. Similarly, top-down grasping is used if
there is no plan from the GrapsNets. From the results in Table 3, we can see
that the Contact-GraspNet-based methods achieve a higher success rate than the
6D GraspNet-based methods. Contact-GraspNet grasps usually have higher quality
by modeling the contact between the gripper with the target. When comparing
the two segmentation methods, MSMFormer achieves higher segmentation accuracy,
as shown in Table 4. However, UCN-based methods have a higher pick-and-place
success rate using 6D GraspNet. We noticed that synthesized grasps using UCN
segmentation is better for 6D GraspNet. This result highlights the importance
of evaluating the whole pipeline in manipulation. It is also interesting to
note that the model-free method #6 achieves a higher grasping success rate
than the model-based methods #1 and #2.

Figure 8: Example failures in our experiment pipelines. Green boxes indicate
the targets for grasping.

Failure Analysis. Fig. 8 shows some examples of different failure types. Table
5 presents a detailed success and failure analysis for each object and each
method. We can see that perception errors and planning errors are dominant and
that perception errors are relatively more frequent. Small and thin objects,
such as scissors and the marker, are more difficult to grasp.

Object | Count | Method 1 | Method 2 | Method 3 | Method 4 | Method 5 | Method 6
---|---|---|---|---|---|---|---
S | PEF | PLF | EF | S | PEF | PLF | EF | S | PEF | PLF | EF | S | PEF | PLF | EF | S | PEF | PLF | EF | S | PEF | PLF | EF
Near-to-far Ordering
003 cracker box | 6 | 5 | - | 1 | - | 1 | 3 | 1 | 1 | 2 | 2 | 2 | - | 3 | 1 | 2 | - | 2 | 3 | 1 | - | 4 | 1 | - | 1
004 sugar box | 5 | 5 | - | - | - | 1 | 4 | - | - | 2 | 2 | 1 | - | 5 | - | - | - | 3 | 1 | 1 | - | 5 | - | - | -
005 tomato soup can | 7 | 6 | 1 | - | - | 6 | 1 | - | - | 3 | - | 4 | - | 6 | - | 1 | - | 2 | - | 5 | - | 2 | 2 | 3 | -
006 mustard bottle | 7 | 6 | 1 | - | - | 3 | 2 | 2 | - | 2 | 1 | 4 | - | 5 | 1 | 1 | - | 1 | - | 5 | 1 | 6 | - | 1 | -
007 tuna fish can | 6 | 1 | 1 | 4 | - | 3 | 2 | 1 | - | 6 | - | - | - | 5 | 1 | - | - | 5 | - | 1 | - | 5 | 1 | - | -
008 pudding box | 5 | 5 | - | - | - | 4 | 1 | - | - | 3 | - | 2 | - | 4 | - | 1 | - | 4 | - | 1 | - | 4 | 1 | - | -
009 gelatin box | 7 | 3 | 4 | - | - | 2 | 4 | 1 | - | 3 | 2 | 1 | 1 | 7 | - | - | - | 4 | - | 3 | - | 6 | - | 1 | -
010 potted meat can | 7 | 6 | 1 | - | - | 3 | 2 | 2 | - | 4 | 1 | 2 | - | 3 | 2 | 1 | 1 | 1 | - | 6 | - | 5 | 2 | - | -
011 banana | 7 | 4 | - | 2 | 1 | 3 | 3 | 1 | - | 1 | - | 6 | - | 2 | - | 5 | - | 5 | - | 2 | - | 6 | - | - | 1
021 bleach cleanser | 5 | 3 | - | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 1 | 1 | 2 | - | 2 | 1 | - | 1 | 3 | 1 | - | 1 | 2 | 2
024 bowl | 7 | 2 | 4 | 1 | - | 5 | 2 | - | - | 5 | - | 2 | - | 7 | - | - | - | 5 | - | 1 | 1 | 6 | - | - | 1
025 mug | 5 | 2 | 1 | - | 2 | 3 | 2 | - | - | 3 | 1 | 1 | - | 1 | 1 | 3 | - | 2 | - | 3 | - | 3 | - | 2 | 1
037 scissors | 7 | 1 | 2 | 4 | - | 1 | 3 | 3 | - | 1 | - | 5 | 1 | 3 | 2 | 2 | - | - | 2 | 5 | - | - | 2 | 2 | 3
035 power drill | 7 | 2 | 1 | 3 | 1 | 3 | 2 | 2 | - | - | 7 | - | - | 2 | 4 | - | 1 | 1 | 3 | 3 | - | 3 | 3 | - | 1
040 large marker | 6 | 1 | 4 | 1 | - | 4 | 1 | 1 | - | 3 | 1 | 2 | - | 1 | 2 | 3 | - | 3 | - | 3 | - | 2 | 2 | 2 | 1
052 extra large clamp | 6 | 6 | - | - | - | 5 | 1 | - | - | 3 | - | 3 | - | 4 | 1 | 1 | - | - | 1 | 5 | - | 2 | 1 | 2 | 1
ALL | 100 | 58 | 20 | 17 | 5 | 48 | 34 | 16 | 2 | 43 | 18 | 36 | 3 | 60 | 15 | 22 | 3 | 38 | 11 | 48 | 3 | 57 | 16 | 15 | 12
Randomly Fixed Ordering
003 cracker box | 6 | 5 | 1 | - | - | 2 | 4 | - | - | 3 | 2 | 1 | - | 4 | 1 | 1 | - | 3 | 2 | 1 | - | 4 | 1 | 1 | -
004 sugar box | 5 | 4 | 1 | - | - | - | 4 | 1 | - | 2 | - | 3 | - | 3 | - | 2 | - | 3 | 1 | 1 | - | 5 | - | - | -
005 tomato soup can | 7 | 7 | - | - | - | 5 | 2 | - | - | 1 | 1 | 5 | - | 6 | 1 | - | - | 1 | - | 5 | 1 | 7 | - | - | -
006 mustard bottle | 7 | 7 | - | - | - | 2 | 4 | 1 | - | 2 | 2 | 2 | 1 | 1 | 1 | 3 | 1 | - | - | 6 | 1 | 3 | - | 1 | 3
007 tuna fish can | 6 | 2 | 4 | - | - | 1 | 5 | - | - | 5 | 1 | - | - | 4 | 1 | 1 | - | 2 | 1 | 3 | - | 4 | 1 | - | 1
008 pudding box | 5 | 4 | - | 1 | - | 3 | 1 | 1 | - | 3 | - | 2 | - | 4 | 1 | - | - | 4 | - | 1 | - | 4 | - | - | 1
009 gelatin box | 7 | 1 | 6 | - | - | 3 | 4 | - | - | 4 | - | 2 | 1 | 7 | - | - | - | 4 | 1 | 2 | - | 6 | - | 1 | -
010 potted meat can | 7 | 7 | - | - | - | 4 | 1 | 2 | - | 2 | 2 | 2 | 1 | 6 | 1 | - | - | 4 | 1 | 2 | - | 4 | - | 2 | 2
011 banana | 7 | 2 | 1 | 4 | - | 2 | 4 | 1 | - | 4 | 1 | 2 | - | 1 | - | 6 | - | 3 | 1 | 2 | 1 | 5 | 1 | 1 | -
021 bleach cleanser | 5 | 3 | 2 | - | - | 1 | 3 | 1 | - | 2 | - | 2 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 3 | - | 1 | - | 2 | 2
024 bowl | 7 | 4 | 3 | - | - | 2 | 3 | 2 | - | 4 | 1 | 2 | - | 7 | - | - | - | 4 | - | 2 | 1 | 7 | - | - | -
025 mug | 5 | 5 | - | - | - | 3 | 2 | - | - | 4 | - | 1 | - | 4 | - | - | 1 | 2 | 1 | 2 | - | 2 | - | 3 | -
037 scissors | 7 | - | 1 | 6 | - | 1 | 3 | 2 | 1 | 1 | 2 | 4 | - | 2 | 2 | 3 | - | 2 | 2 | 3 | - | 2 | 4 | 1 | -
035 power drill | 7 | 2 | 1 | 4 | - | 2 | 2 | 3 | - | - | 6 | - | 1 | 3 | 4 | - | - | - | 3 | 3 | 1 | 4 | 1 | 1 | 1
040 large marker | 6 | - | 5 | 1 | - | 2 | 4 | - | - | - | 1 | 5 | - | 3 | 2 | 1 | - | 2 | 1 | 3 | - | 2 | 4 | - | -
052 extra large clamp | 6 | 6 | - | - | - | 5 | 1 | - | - | 2 | - | 4 | - | 3 | 2 | 1 | - | 1 | - | 5 | - | 2 | 2 | 2 | -
ALL | 100 | 59 | 25 | 16 | - | 38 | 47 | 14 | 1 | 39 | 19 | 37 | 5 | 60 | 17 | 20 | 3 | 36 | 15 | 44 | 5 | 61 | 14 | 15 | 10

Table 5: Statistics of our grasping experiments for each YCB object. S: #pick-
and-place success, PEF: #perception failure, PLF: #planning failure, EF:
#execution failure

##  6 Discussion and Future Work

Limitations. Our SceneReplica benchmark is limited by the objects that are
used for testing, i.e., 16 YCB objects. Ideally, using more diverse objects
can better test robot manipulation systems. Second, our benchmark currently
only supports the Fetch mobile manipulator. Since a head camera is integrated
into the robot, we do not need to perform hand-eye calibration. Extending the
benchmark to robots without cameras would require setting up a third-person
view camera and conducting a hand-eye calibration of the camera. Once the
camera is setup, we can re-render the scene reference images using the new
camera pose, and these images can be used for scene recreation.

Our experiments on SceneReplica hint at several directions to improve robot
pick-and-place. First, object perception and grasp planning accuracy can be
further improved. Second, one important aspect that is not considered in the
model-based and model-free grasping methods is force feedback and force
closure. Slippage failures can be reduced by introducing force feedback. It
can also improve the grasping of fragile objects.

For future work, we plan to continuously evaluate more methods on SceneReplica
and release these results to the community. One line of work that is missing
from our current evaluation is reinforcement learning-based approaches for 6D
grasping. We plan to evaluate some end-to-end grasping approaches on
SceneReplica. We hope the community can use SceneReplica to benchmark robot
manipulation methods. It can also be extended to other manipulation tasks such
as object rearrangement in the future.

#### Acknowledgments

This work was supported in part by the DARPA Perceptually-enabled Task
Guidance (PTG) Program under contract number HR00112220005.

## References

  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Russakovsky et al. [2015] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115:211–252, 2015.
  * Geiger et al. [2013] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun.  Vision meets robotics: The kitti dataset.  _The International Journal of Robotics Research_ , 32(11):1231–1237, 2013.
  * Wang et al. [2018] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  _arXiv preprint arXiv:1804.07461_ , 2018.
  * Wang et al. [2019] A. Wang, Y. Pruksachatkun, N. Nangia, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman.  Superglue: A stickier benchmark for general-purpose language understanding systems.  _Advances in neural information processing systems_ , 32, 2019.
  * Hendrycks et al. [2020] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Kimble et al. [2020] K. Kimble, K. Van Wyk, J. Falco, E. Messina, Y. Sun, M. Shibata, W. Uemura, and Y. Yokokohji.  Benchmarking protocols for evaluating small parts robotic assembly systems.  _IEEE robotics and automation letters_ , 5(2):883–889, 2020.
  * Bottarel et al. [2020] F. Bottarel, G. Vezzani, U. Pattacini, and L. Natale.  Graspa 1.0: Graspa is a robot arm grasping performance benchmark.  _IEEE Robotics and Automation Letters_ , 5(2):836–843, 2020.
  * Calli et al. [2015] B. Calli, A. Singh, A. Walsman, S. Srinivasa, P. Abbeel, and A. M. Dollar.  The ycb object and model set: Towards common benchmarks for manipulation research.  In _2015 international conference on advanced robotics (ICAR)_ , pages 510–517. IEEE, 2015.
  * Bekiroglu et al. [2019] Y. Bekiroglu, N. Marturi, M. A. Roa, K. J. M. Adjigble, T. Pardi, C. Grimm, R. Balasubramanian, K. Hang, and R. Stolkin.  Benchmarking protocol for grasp planning algorithms.  _IEEE Robotics and Automation Letters_ , 5(2):315–322, 2019.
  * Xiang et al. [2017] Y. Xiang, T. Schmidt, V. Narayanan, and D. Fox.  Posecnn: A convolutional neural network for 6d object pose estimation in cluttered scenes.  _arXiv preprint arXiv:1711.00199_ , 2017.
  * Tremblay et al. [2018] J. Tremblay, T. To, B. Sundaralingam, Y. Xiang, D. Fox, and S. Birchfield.  Deep object pose estimation for semantic robotic grasping of household objects.  _arXiv preprint arXiv:1809.10790_ , 2018.
  * Deng et al. [2021] X. Deng, A. Mousavian, Y. Xiang, F. Xia, T. Bretl, and D. Fox.  Poserbpf: A rao–blackwellized particle filter for 6-d object pose tracking.  _IEEE Transactions on Robotics_ , 37(5):1328–1342, 2021.
  * Miller and Allen [2004] A. T. Miller and P. K. Allen.  Graspit! a versatile simulator for robotic grasping.  _IEEE Robotics & Automation Magazine_, 11(4):110–122, 2004.
  * Diankov and Kuffner [2008] R. Diankov and J. Kuffner.  Openrave: A planning architecture for autonomous robotics.  _Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-08-34_ , 79, 2008.
  * Sucan et al. [2012] I. A. Sucan, M. Moll, and L. E. Kavraki.  The open motion planning library.  _IEEE Robotics & Automation Magazine_, 19(4):72–82, 2012.
  * Xie et al. [2020] C. Xie, Y. Xiang, A. Mousavian, and D. Fox.  The best of both modes: Separately leveraging rgb and depth for unseen object instance segmentation.  In _Conference on robot learning_ , pages 1369–1378. PMLR, 2020.
  * Xiang et al. [2021] Y. Xiang, C. Xie, A. Mousavian, and D. Fox.  Learning rgb-d feature embeddings for unseen object instance segmentation.  In _Conference on Robot Learning_ , pages 461–470. PMLR, 2021.
  * Lu et al. [2022] Y. Lu, Y. Chen, N. Ruozzi, and Y. Xiang.  Mean shift mask transformer for unseen object instance segmentation.  _arXiv preprint arXiv:2211.11679_ , 2022.
  * Mousavian et al. [2019] A. Mousavian, C. Eppner, and D. Fox.  6-dof graspnet: Variational grasp generation for object manipulation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2901–2910, 2019.
  * Sundermeyer et al. [2021] M. Sundermeyer, A. Mousavian, R. Triebel, and D. Fox.  Contact-graspnet: Efficient 6-dof grasp generation in cluttered scenes.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 13438–13444. IEEE, 2021.
  * Yu et al. [2020] T. Yu, D. Quillen, Z. He, R. Julian, K. Hausman, C. Finn, and S. Levine.  Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning.  In _Conference on robot learning_ , pages 1094–1100. PMLR, 2020.
  * James et al. [2020] S. James, Z. Ma, D. R. Arrojo, and A. J. Davison.  Rlbench: The robot learning benchmark & learning environment.  _IEEE Robotics and Automation Letters_ , 5(2):3019–3026, 2020.
  * Zhu et al. [2020] Y. Zhu, J. Wong, A. Mandlekar, R. Martín-Martín, A. Joshi, S. Nasiriany, and Y. Zhu.  robosuite: A modular simulation framework and benchmark for robot learning.  _arXiv preprint arXiv:2009.12293_ , 2020.
  * Heo et al. [2023] M. Heo, Y. Lee, D. Lee, and J. J. Lim.  Furniturebench: Reproducible real-world benchmark for long-horizon complex manipulation.  _arXiv preprint arXiv:2305.12821_ , 2023.
  * Liu et al. [2021] Z. Liu, W. Liu, Y. Qin, F. Xiang, M. Gou, S. Xin, M. A. Roa, B. Calli, H. Su, Y. Sun, et al.  Ocrtoc: A cloud-based competition and benchmark for robotic grasping and manipulation.  _IEEE Robotics and Automation Letters_ , 7(1):486–493, 2021.
  * Dasari et al. [2022] S. Dasari, J. Wang, J. Hong, S. Bahl, Y. Lin, A. Wang, A. Thankaraj, K. Chahal, B. Calli, S. Gupta, et al.  Rb2: Robotic manipulation benchmarking with a twist.  _arXiv preprint arXiv:2203.08098_ , 2022.
  * Morgan et al. [2019] A. S. Morgan, K. Hang, W. G. Bircher, F. M. Alladkani, A. Gandhi, B. Calli, and A. M. Dollar.  Benchmarking cluttered robot pick-and-place manipulation with the box and blocks test.  _IEEE Robotics and Automation Letters_ , 5(2):454–461, 2019.
  * Todorov et al. [2012] E. Todorov, T. Erez, and Y. Tassa.  Mujoco: A physics engine for model-based control.  In _2012 IEEE/RSJ international conference on intelligent robots and systems_ , pages 5026–5033. IEEE, 2012.
  * [30] Dawson-Haggerty et al.  trimesh.  URL https://trimsh.org/.
  * wor [2022] International workshop on recovering 6d object pose.  http://cmp.felk.cvut.cz/sixd/workshop_2022/, 2022.

Appendix

##  Appendix A Scene Generation

One of the criteria for our scenes is that each object should be reachable
with respect to the robot arm. In order to accomplish this we discretize the
table’s region into a dense grid and check for each grid location’s
reachability. Next, we only spawn the objects at the selected grid locations
in a randomly sampled stable pose along with a random rotation along global Z
axis. The random rotation along Z axis ensures that even if the same stable
pose is selected for an object, the scenes for it look different. The object
spawning is made collision free by checking for collisions using their 2D
bounding boxes in X-Y plane. Once we have a candidate scene with 5 collision-
free spawned objects, we test motion planning to each of them using the
offline grasp dataset. If any of the objects does not have a feasible motion
plan, we reject the scene and move on with a new scene generation.

This pipeline thus ensures both diverse and feasible scenes. Finally, the set
of 20 scenes is selected from hundreds of candidate scenes using criteria on
an object’s count in the set and a scoring on pose-diversity of the set. While
picking a scene set from the list of generated scene, we ensure that the count
distribution of objects in the set is roughly uniform. Once we have a valid
set of 20 scenes, we then compute the pose-based diversity. For a given set of
20 scenes, we first compute the count of unique poses for each object. This
also gives us a count-based probability distribution using which we compute
the entropy and use that as the scoring function. This ensures that scene-sets
with the same repeated poses for objects are penalized and sets with diversity
are encouraged.

##  Appendix B Grasp and Motion Planning

We used Graspit to compute the 6D-grasps for each object in the benchmark. The
grasps were computed in an offline manner due to the time constraints imposed
by Graspit. Attempting to run Graspit for each iteration in a scene would take
too long time and hence, instead we decided to compute the grasps offline. We
repeatedly run the grasp sampling algorithm until we obtain a desired number
of grasps around the object. Finally, on the initially generated grasp set, we
apply farthest point sampling on grasp translation component to ensure that
the grasps are spread out across an object’s surface. Fig. 9 illustrates the
generated grasps for all 16 YCB objects.

Figure 9: Offline grasps generated using Graspit! for model-based grasping
experiments. Pre-grasp poses shown for better visualization of underlying
object.

In all our experiment pipelines we try top-down grasping in case motion
planning fails for a given grasp. Both model-based top-down grasping and
model-free top-down grasping work in a similar fashion by considering a top-
down view of object’s point cloud. We compute a top-down grasp for an object
by obtaining the two principal components for the point cloud’s X-Y
dimensions. We use the smaller component for obtaining the gripper width and
it also gives the orientation to align the gripper with respect to the object.
The only difference between model-based and model-free top-down grasping is
that with a model-free method, we are restricted to the partial point cloud of
the object. For motion planning obstacles, in model-based grasping we simply
use the estimated pose with the object’s known 3D mesh. In model-free methods
since we don’t have models, one strategy is to simply use the bounding box of
the partial point cloud. However, this did not work well in practice for
cluttered scenes due to large obstacle boxes for motion planning, which then
inevitably fails to find a motion plan to grasp. Hence, we resort to a similar
strategy as used before for top-down grasp alignment and compute an oriented
bounding box using the PCA of object points in X-Y plane.

Figure 10: Top down grasp from point cloud


# Remarks on soft ball packings in dimensions 2 and 3 111Keywords and phrases:
Euclidean $d$-space, Minkowski $d$-space, soft packing, soft parameter, soft
density, soft lattice packing, FCC lattice, Voronoi decomposition, Delaunay
decomposition, refined Molnár decomposition.
2010 Mathematics Subject Classification: 52C15, 52C17, 52C05, 52C07, 52A40.

Károly Bezdek and Zsolt Lángi Partially supported by a Natural Sciences and
Engineering Research Council of Canada Discovery Grant.Partially supported by
the National Research, Development and Innovation Office, NKFI, K-147544 and
BME Water Sciences & Disaster Prevention TKP2020 Institution Excellence
Subprogram, grant no. TKP2020 BME-IKA-VIZ.

###### Abstract

We study translative arrangements of centrally symmetric convex domains in the
plane (resp., of congruent balls in the Euclidean $3$-space) that neither pack
nor cover. We define their soft density depending on a soft parameter and
prove that the largest soft density for soft translative packings of a
centrally symmetric convex domain with $3$-fold rotational symmetry and given
soft parameter is obtained for a proper soft lattice packing. Furthermore, we
show that among the soft lattice packings of congruent soft balls with given
soft parameter the soft density is locally maximal for the corresponding face
centered cubic (FCC) lattice.

##  1 Introduction

Motivated by biological findings, lattice arrangements of congruent balls in
Euclidean $3$-space with pairwise overlaps limited by a properly introduced
parameter (i.e., lattice soft sphere packings), have been studied from the
point of view of largest soft densities. For details see [6] and the
references mentioned there. A similar, but different concept of soft density
has been investigated for not necessarily lattice-type soft packings in [2].
In this note we continue the line of research started in [2] and study the
highest soft densities of soft ball packings in Euclidean $d$-space for
$d=2,3$. In fact, our results are based on the following somewhat more general
concept of soft packings and their soft densities.

######  Definition 1.

Let the Euclidean norm of the $d$-dimensional Euclidean space $\mathbb{E}^{d}$
be denoted by $\|\cdot\|$ and let
$\mathbf{B}^{d}:=\\{\mathbf{x}\in\mathbb{E}^{d}|\|\mathbf{x}\|\leq 1\\}$
denote the (closed) $d$-dimensional unit ball centered at the origin
$\mathbf{o}$ in $\mathbb{E}^{d}$, where $d>1$. Next, let $\mathbf{M}$ be an
arbitrary $\mathbf{o}$-symmetric convex body (i.e., let $\mathbf{M}$ be a
compact, convex set with non-empty interior, and $\mathbf{M}=-\mathbf{M}$) in
$\mathbb{E}^{d}$, $d>1$ and let $\mathbb{M}$ be the $d$-dimensional Minkowski
space (i.e., $d$-dimensional normed space) with $\mathbf{M}$ as its unit ball,
and norm
$\|\mathbf{x}\|_{\mathbb{M}}:=\min\\{\mu>0|\mathbf{x}\in\mu\mathbf{M}\\}$ for
any $\mathbf{x}\in\mathbb{E}^{d}$. Then let
$\mathcal{P}:=\\{\mathbf{c}_{i}+\mathbf{M}\ |\ i=1,2,\dots\ {\rm with}\
\|\mathbf{c}_{j}-\mathbf{c}_{k}\|_{\mathbb{M}}\geq 2\ {\rm for}\ {\rm all}\
1\leq j<k\\}$ be an arbitrary infinite packing of unit balls in $\mathbb{M}$.
Moreover, for any $d\geq 2$ and $\lambda\geq 0$ let
$\mathbf{P}_{\lambda}:=\bigcup_{i=1}^{+\infty}(\mathbf{c}_{i}+(1+\lambda)\mathbf{M})$
denote the outer parallel domain of
$\mathbf{P}:=\bigcup_{i=1}^{+\infty}(\mathbf{c}_{i}+\mathbf{M})$ having outer
radius $\lambda$ in $\mathbb{M}$. Furthermore, let

$\bar{\delta}_{d}(\mathbf{P}_{\lambda}):=\limsup_{R\to+\infty}\frac{\operatorname{vol}_{d}(\mathbf{P}_{\lambda}\cap
R\mathbf{B}^{d})}{\operatorname{vol}_{d}(R\mathbf{B}^{d})}$

be the (upper) density of the outer parallel domain $\mathbf{P}_{\lambda}$
assigned to the unit ball packing $\mathcal{P}$ in $\mathbb{M}$, where
$\operatorname{vol}_{d}(\cdot)$ denotes the $d$-dimensional volume (i.e.,
Lebesgue measure) of the corresponding set in $\mathbb{E}^{d}$. Finally, let

$\bar{\delta}_{\mathbb{M}}(\lambda):=\sup_{\mathcal{P}}\bar{\delta}_{d}(\mathbf{P}_{\lambda})$

be the largest density of the outer parallel domains of unit ball packings
having outer radius $\lambda$ in $\mathbb{M}$. Putting it somewhat
differently, one could say that the family
$\\{\mathbf{c}_{i}+(1+\lambda)\mathbf{M}\ |\ i=1,2,\dots\\}$ of closed balls
of radii $1+\lambda$ is a packing of soft balls with soft parameter $\lambda$
in $\mathbb{M}$, if $\mathcal{P}:=\\{\mathbf{c}_{i}+\mathbf{M}\ |\
i=1,2,\dots\\}$ is a unit ball packing of $\mathbb{M}$ in the usual sense. In
particular, $\bar{\delta}_{d}(\mathbf{P}_{\lambda})$ is called the (upper)
soft density of the soft ball packing
$\\{\mathbf{c}_{i}+(1+\lambda)\mathbf{M}\ |\ i=1,2,\dots\\}$ in $\mathbb{M}$
with $\bar{\delta}_{\mathbf{M}}(\lambda)$ standing for the largest soft
density of packings of soft balls of radii $1+\lambda$ having soft parameter
$\lambda$ in $\mathbb{M}$.

######  Remark 1.

We define $\bar{\delta}_{\mathbb{M}}^{\mathrm{lattice}}(\lambda)$ as the
supremum $\sup_{\mathcal{P}}\bar{\delta}_{d}(\mathbf{P}_{\lambda})$ of all
outer parallel domains of all lattice packings of unit balls in $\mathbb{M}$,
having outer radius $\lambda$.

######  Remark 2.

For any normed space $\mathbb{M}$, the functions
$\bar{\delta}_{\mathbb{M}}(\lambda)$ and
$\bar{\delta}_{\mathbb{M}}^{\mathrm{lattice}}(\lambda)$ are increasing
functions of $\lambda$, the value of $\bar{\delta}_{\mathbb{M}}(0)$ is the
packing density of $\mathbf{M}$, and if $\gamma(\mathbf{M})$ denotes the
simultaneous packing and covering constant of $\mathbf{M}$ ([13]), then
$\gamma(\mathbf{M})-1$ is the smallest value of $\lambda$ with
$\bar{\delta}_{\mathbb{M}}(\lambda)=1$.

By [7] (see also [11], [12]) and [13], for any $\mathbf{o}$-symmetric plane
convex body $\mathbf{M}$, we have that both $\bar{\delta}_{\mathbb{M}}(0)$ and
$\gamma(\mathbf{M})$ are attained for lattice packings of $\mathbf{M}$. Thus,
it is natural to raise

######  Problem 1.

Prove or disprove that
$\bar{\delta}_{\mathbb{M}}(\lambda)=\bar{\delta}_{\mathbb{M}}^{\mathrm{lattice}}(\lambda)$
holds for any $\mathbf{o}$-symmetric plane convex body $\mathbf{M}$ and
$\lambda\geq 0$.

We give an affirmative answer to this question for $\mathbf{o}$-symmetric
plane convex bodies with $3$-fold rotational symmetry as follows.

######  Theorem 1.

For any $\mathbf{o}$-symmetric plane convex body $\mathbf{M}$ with $3$-fold
rotational symmetry and $\lambda\geq 0$, there is a lattice packing
$\mathcal{P}$ of translates of $\mathbf{M}$ such that

$\bar{\delta}_{2}(\mathbf{P}_{\lambda})=\bar{\delta}_{\mathbb{M}}(\lambda).$

In other words, we have
$\bar{\delta}_{\mathbb{M}}(\lambda)=\bar{\delta}_{\mathbb{M}}^{\mathrm{lattice}}(\lambda)$
for any $\mathbf{o}$-symmetric plane convex body $\mathbf{M}$ with $3$-fold
rotational symmetry and $\lambda\geq 0$.

######  Remark 3.

As a special case it was proved in [2] that
$\bar{\delta}_{\mathbb{E}^{3}}(\lambda)=\bar{\delta}_{\mathbb{E}^{3}}^{\mathrm{lattice}}(\lambda)$
holds for all $\lambda\geq 0$, which is attained for a regular triangle
lattice packing of soft disks with soft parameter $\lambda$ in
$\mathbb{E}^{2}$.

The analogue of Problem 1 in dimensions $3$ and higher is wide open, even for
Euclidean balls. We have the following partial results on soft ball packings
in $\mathbb{E}^{3}$.

On the one hand, Böröczky [3] has proved that
$\gamma(\mathbf{B}^{3})=\sqrt{\frac{5}{3}}$, which is attained for a BCC
lattice packing of $\mathbf{B}^{3}$. This implies that
$\bar{\delta}_{\mathbb{E}^{3}}(\lambda)=\bar{\delta}_{\mathbb{E}^{3}}^{\mathrm{lattice}}(\lambda)=1$
holds for all $\sqrt{\frac{5}{3}}-1=0.2909...\leq\lambda$. On the other hand,
Theorems 5 and 6 of [2] give upper bounds strictly less than $1$ for
$\bar{\delta}_{\mathbb{E}^{3}}(\lambda)$ and for any
$0\leq\lambda\leq\sqrt{\frac{3}{2}}-1=0.2247...$. This leaves us with the
trivial upper bound $\bar{\delta}_{\mathbb{E}^{3}}(\lambda)\leq 1$ for any
$\sqrt{\frac{3}{2}}-1=0.2247...<\lambda<\sqrt{\frac{5}{3}}-1=0.2909...$. This
trivial upper bound is improved by

######  Theorem 2.

Let $0<\lambda<\sqrt{\frac{5}{3}}-1=0.2909...$. Then
$\bar{\delta}_{\mathbb{E}^{3}}^{\mathrm{lattice}}(\lambda)\leq\bar{\delta}_{\mathbb{E}^{3}}(\lambda)\leq
1-\left(\frac{\sqrt{\frac{5}{3}}-1-\lambda}{11\sqrt{\frac{5}{3}}+3-\lambda}\right)^{3}$.

Last but not least, we have

######  Theorem 3.

For any $\lambda>0$, among lattice packings of soft balls with soft parameter
$\lambda$ in $\mathbb{E}^{3}$, the soft density function has a local maximum
at the corresponding face centered cubic (FCC) lattice.

Hence, it is natural to put forward

######  Problem 2.

Prove or disprove that there exists $\lambda_{0}>0$ such that for any
$0<\lambda\leq\lambda_{0}$, among all packings of soft balls with soft
parameter $\lambda$ in $\mathbb{E}^{3}$, the soft density function has a
maximum at the corresponding FCC lattice.

######  Remark 4.

We note that the method of the proof of Theorem 3 presented in Section 4 works
under two conditions: every facet of the Dirichlet-Voronoi cell of a ball
belongs to a minimal vector of the lattice, and that the symmetry group of the
lattice acts transitively on the faces. Thus, Theorem 3 holds also for all
known densest lattice packings, namely for the $D_{4},D_{5},E_{6},E_{7},E_{8}$
lattices and the Leech lattice.

In the rest of this note we prove the theorems stated.

##  2 Proof of Theorem 1

The proof relies on the properties of Voronoi and Delaunay tesselations in
normed planes; for a broader introduction on this topic, the interested reader
is referred to [1] or [9]. Without loss of generality, we may assume that the
unit disk $\mathbf{M}$ of the normed plane $\mathbb{M}$ is smooth and strictly
convex. Observe that in this case, for any points $\mathbf{p}\neq\mathbf{q}$,
any line parallel to $[\mathbf{p},\mathbf{q}]$ contains a unique point whose
$\mathbf{M}$-distance from $\mathbf{p}$ and $\mathbf{q}$ are equal, where
$[\mathbf{p},\mathbf{q}]$ stands for the (closed) line segment connecting the
points $\mathbf{p}$ and $\mathbf{q}$. Thus, the bisector of any segment is
homeomorphic to a line. Furthermore, we assume that
$0<\lambda<\gamma(\mathbf{M})-1$, as otherwise the statement of Theorem 1 is
trivial.

Let $\mathcal{C}\subset\mathbb{M}$ be a point set such that
$\mathcal{P}=\\{\mathbf{c}+\mathbf{M}:\mathbf{c}\in\mathcal{C}\\}$ is a
packing of translates of $\mathbf{M}$. We show that there is a lattice packing
$\mathcal{P}^{\prime}$ satisfying
$\bar{\delta}_{2}(\mathbf{P}_{\lambda})\leq\bar{\delta}_{2}(\mathbf{P}^{\prime}_{\lambda})$.
Clearly, we may assume that $\mathcal{P}$ is _saturated_ , i.e. the
$\mathbf{M}$-distance of any point of $\mathbb{M}$ is strictly less than two
from some point of $\mathcal{C}$, as otherwise we may add additional
translates of $\mathbf{M}$ to $\mathcal{P}$.

For any $\mathbf{c}\in\mathcal{C}$, the _Voronoi cell_ of $\mathcal{C}$ is
defined in the usual way as
$V_{\mathbf{c}}=\\{\mathbf{x}\in\mathbb{M}:||\mathbf{x}-\mathbf{c}||_{\mathbf{M}}\leq||\mathbf{x}-\mathbf{c}^{\prime}||_{\mathbf{M}}\hbox{
for any }\mathbf{c}^{\prime}\in\mathcal{C}\\}$. The Voronoi cell of a point
$\mathbf{c}$ is not necessarily convex, but it is starlike with respect to
$\mathbf{c}$; i.e. it satisfies the property that for any $\mathbf{x}\in
V_{\mathbf{c}}$, $[\mathbf{c},\mathbf{x}]\subset V_{\mathbf{c}}$ holds. It is
also known that in the above case the Voronoi cells of the points of
$\mathcal{C}$ form a locally finite decomposition of $\mathbb{M}$. The
_Delaunay tessellation_ associated to $\mathcal{C}$ is the ‘dual’ of of the
Voronoi decomposition; in this two points
$\mathbf{c},\mathbf{c}^{\prime}\in\mathcal{C}$ are connected by the edge
$[\mathbf{c},\mathbf{c}^{\prime}]$ if and only if the unique smallest
homothetic copy of $\mathbf{M}$ containing $\mathbf{c},\mathbf{c}^{\prime}$
contains no other point of $\mathcal{C}$. This also defines a locally finite
decomposition of $\mathbb{M}$ into convex polygons, called _Delaunay cells_ ,
which satisfy the following (see also [9]):

  * (i)

the vertices of any Delaunay cell $F$ are points in $\mathcal{C}$;

  * (ii)

for any Delaunay cell $F$ there is a homothetic copy
$\mathbf{x}+\lambda\mathbf{M}$, containing all vertices of $F$ in its
boundary, which contains no point of $\mathcal{C}$ apart from the vertices of
$F$; this homothet is called the _circumdisk_ of $F$.

In the next part we introduce another locally finite, edge-to-edge
decomposition, which we call the _Molnár decomposition_ , as follows. This
decomposition, in the case that $\mathbf{M}$ is a Euclidean disk, was
introduced in [10].

Let $F$ be a cell of the Delaunay decomposition, and let us denote the
circumdisk of $F$ by $\mathbf{M}_{F}\subset\mathbb{M}$, and the center of
$\mathbf{M}_{F}$ by $\mathbf{o}_{F}$. If $F$ does not contain
$\mathbf{o}_{F}$, then there is a unique side of $F$ that separates it from
$F$ in $\mathbf{M}_{F}$. We call this side a _separating side_ of $F$. If
$[\mathbf{c}_{i},\mathbf{c}_{j}]$ is a separating side of $F$, then we call
the polygonal curve
$[\mathbf{c}_{i},\mathbf{o}_{F}]\cup[\mathbf{o}_{F},\mathbf{c}_{j}]$ the
_bridge_ associated to the separating side $[\mathbf{c}_{i},\mathbf{c}_{j}]$
of $F$ (cf. Figure 1).

Figure 1: An illustration for the Molnár decomposition of a point system in
the case that $\mathbf{M}$ is a Euclidean disk. In the figure, the edges of
the cells, the circumcircles of the cells and the separating sides are denoted
by solid, dotted and dashed lines, respectively.

Our main lemma about the Molnár decomposition is the following.

######  Lemma 1.

If we replace all separating sides of a Delanuay decomposition by the
corresponding bridges, we obtain a locally finite, edge-to-edge decomposition
of $\mathbb{M}$.

###### Proof.

As in [10], the proof is based on showing the following two statements.

  * (a)

Bridges may intersect only at their endpoints.

  * (b)

A bridge may intersect an edge in the Molnár decomposition only at its
endpoints.

To show (a), recall that for any cell $F$, the points of $\mathcal{C}$ closest
to $\mathbf{o}_{F}$ (measured in normed distance) are exactly the vertices of
$F$. Thus, if $[\mathbf{o}_{F},\mathbf{c}_{i}]$ and
$[\mathbf{o}_{F^{\prime}},\mathbf{c}_{j}]$ are components of bridges with
$\mathbf{c}_{i}\neq\mathbf{c}_{j}$ and
$\mathbf{o}_{F}\neq\mathbf{o}_{F^{\prime}}$, then $\mathbf{c}_{i}$ is closer
to $\mathbf{o}_{F}$ than to $\mathbf{o}_{F^{\prime}}$, and $\mathbf{c}_{j}$ is
closer to $\mathbf{o}_{F^{\prime}}$ than to $\mathbf{o}_{F}$. Hence, if $Z$ is
the set of points in $\mathbb{M}$ closer to $\mathbf{o}_{F}$ than to
$\mathbf{o}_{F^{\prime}}$, then $Z$ contains $[\mathbf{o}_{F},\mathbf{c}_{i}]$
but it is disjoint from $[\mathbf{o}_{F^{\prime}},\mathbf{c}_{j}]$, implying
that $[\mathbf{o}_{F},\mathbf{c}_{i}]$ and
$[\mathbf{o}_{F^{\prime}},\mathbf{c}_{j}]$ are disjoint.

Now, we show (b), and let $[\mathbf{c}_{i},\mathbf{c}_{j}]$ be a separating
side of the cell $F$. First, observe that by the definition of separating
side, the triangle $T$ with vertices $\mathbf{c}_{i}$, $\mathbf{c}_{j}$ and
$\mathbf{o}_{F}$ intersects finitely many cells of the Delaunay-decomposition
at a point different from $[\mathbf{c}_{i},\mathbf{c}_{j}]$, each of which is
different from $F$. Let $F^{\prime}$ be the cell adjacent to $F$ and having
$[\mathbf{c}_{i},\mathbf{c}_{j}]$ as a side. Let $\mathbf{M}_{F^{\prime}}$ be
the circumdisk of $F^{\prime}$. By the properties of bisectors and Voronoi
cells described in the beginning of the section, the triangle
$T=\operatorname{conv}\\{\mathbf{c}_{i},\mathbf{c}_{j},\mathbf{o}_{F}\\}$ is
contained in $\mathbf{M}_{F^{\prime}}$, and it is easy to see that it is
contained also in the interior of
$T^{\prime}=\operatorname{conv}\\{\mathbf{c}_{i},\mathbf{c}_{j},\mathbf{o}_{F^{\prime}}\\}$
apart from $[\mathbf{c}_{i},\mathbf{c}_{j}]$. Thus, if
$\mathbf{o}_{F^{\prime}}\in F^{\prime}$, then
$T\setminus[\mathbf{c}_{i},\mathbf{c}_{j}]\subseteq\operatorname{int}(F^{\prime})$,
and (b) clearly holds for the bridge associated to
$[\mathbf{c}_{i},\mathbf{c}_{j}]$. On the other hand, if
$\mathbf{o}_{F^{\prime}}\notin F^{\prime}$, then there is a separating side
$[\mathbf{c}_{i^{\prime}},\mathbf{c}_{j^{\prime}}]$ of $F^{\prime}$, removed
during the construction, and this side is the unique side containing any point
of the bridge apart from $\mathbf{c}_{i}$ and $\mathbf{c}_{j}$. Thus, no side
of $F^{\prime}$ in the Molnár decomposition contains an interior point of the
bridge. Furthermore, observe that if any side in the Molnár decomposition
contains an interior point of
$[\mathbf{c}_{i},\mathbf{o}_{F}]\cup[\mathbf{o}_{F},\mathbf{c}_{j}]$, then it
also contains an interior point of
$[\mathbf{c}_{i^{\prime}},\mathbf{o}_{F^{\prime}}]\cup[\mathbf{o}_{F^{\prime}},\mathbf{c}_{j^{\prime}}]$.
Consequently, we may repeat the argument with $F^{\prime}$ playing the role of
$F$, and since only finitely many cells may intersect $T$ at a point different
from $[\mathbf{c}_{i},\mathbf{c}_{j}]$, and each such cell is different from
$F$, we conclude that
$[\mathbf{c}_{i},\mathbf{o}_{F}]\cup[\mathbf{o}_{F},\mathbf{c}_{j}]$ may
intersect any side of the Molnár decomposition only at $\mathbf{c}_{i}$ or
$\mathbf{c}_{j}$. ∎

Let $[\mathbf{c}_{i},\mathbf{c}_{j}]$ be an edge of a Delaunay cell $F$, and
let $T(\mathbf{c}_{i},\mathbf{c}_{j})$ be an equilateral triangle with
edgelength $2$ such that an edge of $T(\mathbf{c}_{i},\mathbf{c}_{j})$ is
parallel to $[\mathbf{c}_{i},\mathbf{c}_{j}]$. Clearly, the circumradius of
$T(\mathbf{c}_{i},\mathbf{c}_{j})$, which we denote by
$R(\mathbf{c}_{i},\mathbf{c}_{j})$, is not greater than the circumradius of
$F$. Furthermore, as $\mathbf{M}$ has $3$-fold rotational symmetry,
$T(\mathbf{c}_{i},\mathbf{c}_{j})$ is a regular triangle in the underlying
Euclidean norm as well.

Let us dissect every cell $F$ of the Molnár decomposition by connecting the
circumcenter of the corresponding Delaunay cell to each vertex of $F$. We call
the so-obtained decomposition the _refined Molnár decomposition_ associated to
$\mathcal{C}$. Note that then every cell $F$ of this decomposition is of the
form
$\operatorname{cl}\left(\operatorname{conv}\\{\mathbf{a},\mathbf{b},\mathbf{c}\\}\setminus\operatorname{conv}\\{\mathbf{a},\mathbf{b},\mathbf{c}^{\prime}\\}\right)$,
where $\mathbf{a},\mathbf{b}\in\mathcal{C}$, $\mathbf{c}$ is the center of a
Delaunay cell, and $\mathbf{c}^{\prime}$ is the center of another Delaunay
cell or the midpoint of $[\mathbf{a},\mathbf{b}]$, furthermore, we have
$2>||\mathbf{b}-\mathbf{c}||_{\mathbf{M}}=||\mathbf{a}-\mathbf{c}||_{\mathbf{M}}\geq
R(\mathbf{a},\mathbf{b})$,
$||\mathbf{b}-\mathbf{c}^{\prime}||_{\mathbf{M}}=||\mathbf{a}-\mathbf{c}^{\prime}||_{\mathbf{M}}$,
and $||\mathbf{a}-\mathbf{b}||_{\mathbf{M}}\geq 2$. We note that since
$0<\lambda<\gamma(\mathbf{M})-1$, $\mathbf{c}$ does not lie in the interior of
any soft disk centered at a point of $\mathcal{C}$. We set

$\delta(F):=\frac{\operatorname{vol}_{2}\left(\left((\mathbf{a}+(1+\lambda)\mathbf{M})\cup(\mathbf{b}+(1+\lambda)\mathbf{M})\right)\cap
F\right)}{\operatorname{vol}_{2}(F)}.$

To prove Theorem 1, it is sufficient to prove that for any cell $F$,
$\delta(F)$ is maximal with the direction of $[\mathbf{a},\mathbf{b}]$ fixed,
if and only if $||\mathbf{a}-\mathbf{b}||_{\mathbf{M}}=2$,
$\mathbf{c}^{\prime}$ is the midpoint of $[\mathbf{a},\mathbf{b}]$, and
$||\mathbf{b}-\mathbf{c}||_{\mathbf{M}}=||\mathbf{a}-\mathbf{c}||_{\mathbf{M}}=R(\mathbf{a},\mathbf{b})$.
This statement is an immediate consequence of Lemma 2 and 3, and it implies
that
$\bar{\delta}_{\mathbb{M}}(\lambda)=\bar{\delta}_{\mathbb{M}}^{\mathrm{lattice}}(\lambda)$,
which is attained by a regular triangle lattice packing of soft disks with
soft parameter $\lambda$ in $\mathbb{M}$.

######  Lemma 2.

Let $T=\operatorname{conv}\\{\mathbf{a},\mathbf{b},\mathbf{c}\\}$ and
$T^{\prime}=\operatorname{conv}\\{\mathbf{a},\mathbf{b},\mathbf{c}^{\prime}\\}$
be isosceles triangles (in the norm of $\mathbb{M}$) with base
$[\mathbf{a},\mathbf{b}]$, where $||\mathbf{a}-\mathbf{b}||_{\mathbf{M}}\geq
2$, and assume that $\mathbf{c}$ is farther from $\mathbf{a},\mathbf{b}$ than
$\mathbf{c}^{\prime}$. Let
$\rho(T):=\frac{\operatorname{vol}_{2}\left(T\cap\left((\mathbf{a}+(1+\lambda)\mathbf{M})\cup(\mathbf{b}+(1+\lambda)\mathbf{M})\right)\right)}{\operatorname{vol}_{2}(T)}$,
and define $\rho(T^{\prime})$ similarly. Then $\rho(T)\leq\rho(T^{\prime})$,
with equality if and only if
$T\subseteq(\mathbf{a}+(1+\lambda)\mathbf{M})\cup(\mathbf{b}+(1+\lambda)\mathbf{M})$.

###### Proof.

Without loss of generality, we may assume that $\mathbf{c}^{\prime}\in T$. Let
$||\mathbf{c}^{\prime}-\mathbf{b}||_{\mathbf{M}}=||\mathbf{c}^{\prime}-\mathbf{a}||_{\mathbf{M}}=\mu$.
We consider only the case that $\mu\geq 1+\lambda$, in the opposite case a
similar argument can be given. Note that under this condition the density
$\rho(T^{\prime})$ of
$(\mathbf{a}+(1+\lambda)\mathbf{M})\cup(\mathbf{b}+(1+\lambda)\mathbf{M})$ in
$T^{\prime}$ is greater than $\frac{(1+\lambda)^{2}}{\mu^{2}}$, and in the
region $\operatorname{cl}(T\setminus T^{\prime})$ it is less than
$\frac{(1+\lambda)^{2}}{\mu^{2}}$ (see Figure 3). This implies the assertion.
∎

Figure 2: An illustration for Lemma 2. The dotted line indicates the bisector
of $[\mathbf{a},\mathbf{b}]$. Dashed lines show the boundaries of
$\mathbf{a}+\mu\mathbf{M}$ and $\mathbf{b}+\mu\mathbf{M}$.

Figure 3: An illlustration for Remark 5 for the case
$\mathbf{x}=\mathbf{x}^{\prime}$.

Before our next lemma, we make a remark, where for any
$\mathbf{p},\mathbf{q}\in\operatorname{bd}\mathbf{M}$ which are not antipodal,
$\widehat{\mathbf{p}\mathbf{q}}$ denotes the shorter arc in
$\operatorname{bd}\mathbf{M}$ connecting $\mathbf{p}$ and $\mathbf{q}$.

######  Remark 5.

Let
$\mathbf{x},\mathbf{x}^{\prime},\mathbf{y}^{\prime},\mathbf{y}\in\operatorname{bd}\mathbf{M}$
in this counterclockwise order in $\operatorname{bd}\mathbf{M}$ such that no
two of them are antipodal,
$\widehat{\mathbf{x}^{\prime}\mathbf{y}^{\prime}}\subsetneq\widehat{\mathbf{x}\mathbf{y}}$,
and $\mathbf{x}^{\prime}\neq\mathbf{y}^{\prime}$. Let $A$ be the linear
transformation defined by $A(\mathbf{x})=\mathbf{x}^{\prime}$ and
$A(\mathbf{y})=\mathbf{y}^{\prime}$. Then
$A(\widehat{\mathbf{x}\mathbf{y}})\cap\operatorname{int}\mathbf{M}=\emptyset$,
and
$A(\widehat{\mathbf{y}(-\mathbf{x})})\setminus\\{\mathbf{y}^{\prime},-\mathbf{x}^{\prime}\\},A(\widehat{(-\mathbf{y})\mathbf{x}})\setminus\\{-\mathbf{y}^{\prime},\mathbf{x}^{\prime}\\}\subset\operatorname{int}\mathbf{M}$.

###### Proof.

The proof is based on two observations. First, note that without loss of
generality, we may assume that $\mathbf{x}=\mathbf{x}^{\prime}$. Second, we
observe that when $\mathbf{y}$ moves to $\mathbf{y}^{\prime}$ under $A$, every
point of $\widehat{\mathbf{x}\mathbf{y}}$ is translated by a positive scalar
multiple of the vector $\mathbf{y}^{\prime}-\mathbf{y}$. This shows that
$A(\widehat{\mathbf{x}\mathbf{y}})$ is disjoint from
$\operatorname{int}\mathbf{M}$. To prove the second statement, we may apply a
similar argument. ∎

######  Lemma 3.

Let $T=\operatorname{conv}\\{\mathbf{a},\mathbf{b},\mathbf{c}\\}$ and
$T^{\prime}=\operatorname{conv}\\{\mathbf{a}^{\prime},\mathbf{b}^{\prime},\mathbf{c}\\}$
be isosceles triangles such that their bases $[\mathbf{a},\mathbf{b}]$ and
$[\mathbf{a}^{\prime},\mathbf{b}^{\prime}]$ are parallel,
$||\mathbf{c}-\mathbf{b}||_{\mathbf{M}}=||\mathbf{c}-\mathbf{a}||_{\mathbf{M}}=||\mathbf{c}-\mathbf{b}^{\prime}||_{\mathbf{M}}=||\mathbf{c}-\mathbf{a}^{\prime}||_{\mathbf{M}}=\tau>1+\lambda$,
and
$||\mathbf{b}-\mathbf{a}||_{\mathbf{M}}\geq||\mathbf{b}^{\prime}-\mathbf{a}^{\prime}||_{\mathbf{M}}\geq
2$. Let
$\rho(T):=\frac{\operatorname{vol}_{2}\left(T\cap\left((a+(1+\lambda)\mathbf{M})\cup(b+(1+\lambda)\mathbf{M})\right)\right)}{\operatorname{vol}_{2}(T)}$,
and define $\rho(T^{\prime})$ similarly. Then $\rho(T)\leq\rho(T^{\prime})$,
with equality if and only if
$[\mathbf{a},\mathbf{b}]=[\mathbf{a}^{\prime},\mathbf{b}^{\prime}]$.

###### Proof.

Without loss of generality, we may assume that $\mathbf{c}=\mathbf{o}$, and
$\mathbf{a},\mathbf{a}^{\prime},\mathbf{b}^{\prime},\mathbf{b},-\mathbf{a}$
are in this counterclockwise order around $\mathbf{o}$ in
$\tau\operatorname{bd}\mathbf{M}$. Let $A$ be the linear transformation
defined by $A(\mathbf{a})=\mathbf{a}^{\prime}$,
$A(\mathbf{b})=\mathbf{b}^{\prime}$. Then $A(T)=T^{\prime}$, and by Remark 5,
we have $A(\mathbf{a}+(1+\lambda)\mathbf{M})\cap
T^{\prime}\subseteq(\mathbf{a}^{\prime}+(1+\lambda)\mathbf{M})\cap T^{\prime}$
and $A(\mathbf{b}+(1+\lambda)\mathbf{M})\cap
T^{\prime}\subseteq(\mathbf{b}^{\prime}+(1+\lambda)\mathbf{M})\cap
T^{\prime}$. Since $A$ is nondegenerate, and a nondegenerate linear
transformation does not change the ratio of areas of figures, it follows that
$\rho(T)\leq\rho(T^{\prime})$. Furthermore, $\rho(T)=\rho(T^{\prime})$ implies
$A(\mathbf{a}+(1+\lambda)\mathbf{M})\cap
T^{\prime}=(\mathbf{a}^{\prime}+(1+\lambda)\mathbf{M})\cap T^{\prime}$ and
$A(\mathbf{b}+(1+\lambda)\mathbf{M})\cap
T^{\prime}=(\mathbf{b}^{\prime}+(1+\lambda)\mathbf{M})\cap T^{\prime}$, which
in turn yields that $\mathbf{a}=\mathbf{a}^{\prime}$ and
$\mathbf{b}=\mathbf{b}^{\prime}$. ∎

This completes the proof of Theorem 1.

##  3 Proof of Theorem 2

We start proving

######  Theorem 4.

Let $\mathcal{P}$ be a unit ball packing in $\mathbb{E}^{3}$, and let
$0<\lambda<\sqrt{\frac{5}{3}}-1=0.290994...$. Then any ball of radius
$R_{\lambda}:=11\sqrt{\frac{5}{3}}+3-\lambda$ contains a ball of radius
$\sqrt{\frac{5}{3}}-1-\lambda$ that does not overlap $\mathcal{P}_{\lambda}$.

###### Proof.

Consider a packing $\mathcal{P}$, which, without loss of generality, we assume
to be saturated, and let $B:=\mathbf{c}+R_{\lambda}\mathbf{B}^{3}$ be the ball
of radius $R_{\lambda}$ and center $\mathbf{c}$. We show that the ball
$\bar{B}:=\mathbf{c}+\left(10\sqrt{\frac{5}{3}}+4\right)\mathbf{B}^{3}$
contains a vertex of a Diriclet-Voronoi cell (in short, DV-cell) of
$\mathcal{P}$ whose distance from the centers of the balls of $\mathcal{P}$ is
at least $\sqrt{\frac{5}{3}}$.

Let $V$ be a DV-cell that contains $\mathbf{c}$, and call a DV-cell
$V^{\prime}$ a $k$-neighbor of $V$ if there is a continuous curve, starting at
an interior point of $V$ and ending at an interior point of $V^{\prime}$ that
contains the points of at most $k-1$ other DV-cells of $\mathcal{P}$. In
particular, we say that $V$ is a $0$-neighbor of itself. Notice that the
distance of any vertex of a DV-cell from its center is at most $2$, and if it
is at most $\sqrt{\frac{5}{3}}$, then the diameter of the cell is at most
$2\sqrt{\frac{5}{3}}$. It follows that if $V$ has a $k$-neighbor with $k\leq
5$, which has a vertex at least $\sqrt{\frac{5}{3}}$ far from the centers of
the balls of $\mathcal{P}$, then $\bar{B}$ contains a vertex which is at least
$\sqrt{\frac{5}{3}}$ far from the unit ball centers. So, assume that no
$k$-neighbor of $V$, with $k\leq 5$, has a vertex at a distance at least
$\sqrt{\frac{5}{3}}$ from the centers of the balls in $\mathcal{P}$. We are
going to derive a contradiction from it, which then completes the proof of
Theorem 4. In what follows $k\leq 5$.

Consider a vertex $\mathbf{p}$ of a $k$-neighbor of $V$. Then, by the same
argument as in [3] (see the second paragraph on page 87), $\mathbf{p}$ belongs
to at most four DV-cells of $\mathcal{P}$. The third paragraph on page 87 of
[3] implies that the faces of a $k$-neighbor of $V$ are at most hexagons.

We show that there is a $k$-neighbor of $V$ which has a hexagon face.
Similarly like in [3] (see the fourth paragraph on page 87), by Euler’s
formula if a DV-cell has more than 12 faces, then it has a face with more than
$5$ vertices, which must be, by the considerations above, a hexagon. Using the
argument in [3] (see the fifth paragraph on page 87), if a $k$-neighbor
$\bar{V}$ of $V$ has less than $11$ faces, then it has a vertex at a distance
greater than $\sqrt{\frac{5}{3}}$ from the center of $\bar{V}$, which
contradicts our assumption. Using the sixth paragraph on page 87 in [3], the
possibility that $\bar{V}$ has $11$ faces is exluded by Lemma 2 of [3]. Based
on the last paragraph of page 87 in [3], consider the case that each
$k$-neighbor of $V$ has exactly $12$ faces, and each face is a pentagon. Using
the idea of Lemma 3 of [3], starting with $V$ we can construct a cell-complex
$\mathcal{P}$ isomorphic to that of the regular 120-cell in $\mathbb{E}^{4}$.
Note that then each cell in $\mathcal{P}$ is a $k$-neighbor of $V$, with
$k\leq 5$. Thus, at each vertex in this complex, exactly four cells of
$\mathcal{P}$ meet, which, similarly like in the proof of Lemma 3 of [3],
yields a contradiction.

Thus, we can conclude that a $k$-neighbor of $V$ has a hexagon face. Then
similarly like in [3] (see page 88), a vertex of this hexagon has distance at
least $\sqrt{\frac{5}{3}}$ from the center of the cell, which contradicts our
assumption. This completes the proof of Theorem 4. ∎

Now, let $\mathcal{P}$ be a unit ball packing in $\mathbb{E}^{3}$, and let
$0<\lambda<\sqrt{\frac{5}{3}}-1$. We are going to show that
$\bar{\delta}_{3}(\mathcal{P}_{\lambda})\leq
1-\frac{\left(\sqrt{\frac{5}{3}}-1-\lambda\right)^{3}}{R_{\lambda}^{3}}$. The
details are as follows.

Let
$\delta_{\lambda}:=1-\frac{\left(\sqrt{\frac{5}{3}}-1-\lambda\right)^{3}}{R_{\lambda}^{3}}$.
By Theorem 4, it follows that any ball of radius $R_{\lambda}$ contains a ball
of radius $\sqrt{\frac{5}{3}}-1-\lambda$ that does not overlap
$\mathcal{P}_{\lambda}$. In other words, we have that

$\frac{\int_{\mathbf{z}+R_{\lambda}\mathbf{B}^{3}}\chi_{\mathcal{P}_{\lambda}}(\mathbf{y})\,d\mathbf{y}}{\frac{4}{3}R_{\lambda}^{3}\pi}\leq\delta_{\lambda}$

for any $\mathbf{z}\in\mathbb{E}^{3}$, where $\chi_{\mathcal{P}_{\lambda}}$ is
the indicator function of $\mathcal{P}_{\lambda}$.

Let $R>0$ be sufficiently large. Then the density of $\mathcal{P}_{\lambda}$
in $R\mathbf{B}^{3}$ is

$\frac{\int_{R\mathbf{B}^{3}}\chi_{\mathcal{P}_{\lambda}}(\mathbf{y})\,d\mathbf{y}}{\frac{4}{3}R^{3}\pi}=\frac{\int_{R\mathbf{B}^{3}}\int_{\mathbf{y}+R_{\lambda}\mathbf{B}^{3}}\chi_{\mathcal{P}_{\lambda}}(\mathbf{y})\,d\mathbf{z}\,d\mathbf{y}}{\frac{16}{9}R^{3}R_{\lambda}^{3}\pi^{2}}=\frac{\int_{(R+R_{\lambda})\mathbf{B}^{3}}\int_{(\mathbf{z}+R_{\lambda}\mathbf{B}^{3})\cap
R\mathbf{B}^{3}}\chi_{\mathcal{P}_{\lambda}}(\mathbf{y})\,d\mathbf{y}\,d\mathbf{z}}{\frac{16}{9}R^{3}R_{\lambda}^{3}\pi^{2}}\leq$
$\leq\frac{\int_{(R+R_{\lambda})\mathbf{B}^{3}}\delta_{\lambda}\,d\mathbf{z}}{\frac{4}{3}R^{3}\pi}=\delta_{\lambda}\cdot\left(1+\frac{R_{\lambda}}{R}\right)^{3}.$

This completes the proof of Theorem 2.

##  4 Proof of Theorem 3

In the proof we use the following formula of Csikós, stated as Theorem 4.1 in
[5].

######  Theorem 5.

Let
$\\{\mathbf{B}_{i}^{d}=\mathbf{x}_{i}+r_{i}\mathbf{B}^{d}:i=1,2,\ldots,n\\}$
be a family of balls in $\mathbb{E}^{d}$. For any value $i$ and point
$\mathbf{p}\in\mathbb{E}^{d}$, set
$K_{i}(\mathbf{p})=\|\mathbf{x}_{i}-\mathbf{p}\|^{2}-r_{i}^{2}$. For any $i$,
let $C_{i}=\\{\mathbf{p}\in\mathbb{E}^{d}:K_{i}(\mathbf{p})\leq
K_{j}(\mathbf{p}),j=1,2,\ldots,n\\}$ be the _weighted Dirichlet-Voronoi_ cell
of $\mathbf{B}_{i}^{d}$. If $i\neq j$, the set $W_{ij}=C_{i}\cap
C_{j}\cap\mathbf{B}_{i}^{d}\cap\mathbf{B}_{j}^{d}$ is called the _wall_
between $\mathbf{B}_{i}^{d}$ and $\mathbf{B}_{j}^{d}$. Let
$\gamma_{i}:(a,b)\to\mathbb{E}^{d}$, $i=1,2,\ldots,n$ be smooth curves, and
$t_{0}\in(a,b)$ be a value such that the points
$\gamma_{i}(t_{0})=\mathbf{x}_{i}$ are pairwise distinct. Then the function
$v(t):=\operatorname{vol}_{d}\left(\bigcup_{i=1}^{n}\left(\gamma_{i}(t)+r_{i}\mathbf{B}^{d}\right)\right)$
is differentiable at $t_{0}$, and its derivative is

$v^{\prime}(t_{0})=\sum_{1\leq i<j\leq
n}\|\gamma_{i}(t_{0})-\gamma_{j}(t_{0})\|^{\prime}\cdot\operatorname{vol}_{d-1}\left(W_{ij}\right).$

We note that Theorem 5 remains valid for one-sided derivatives at $a$ and $b$
if the curves $\gamma_{i}$ are defined in the interval $[a,b]$.

Let $\mathcal{F}$ be an FCC lattice packing of soft balls containing the soft
ball $(1+\lambda)\mathbf{B}^{3}$ such that $\mathbf{B}^{3}$ is touched by the
unit balls $\\{\mathbf{B}_{i}^{3}:i=1,2,\ldots,12\\}$ concentric to $12$ soft
balls of $\mathcal{F}$. Moreover, let $V$ be the Dirichlet-Voronoi cell of
$\mathbf{B}^{3}$ in $\mathcal{F}$. Without loss of generality, we may assume
that $\lambda$ is chosen such that the soft balls of $\mathcal{F}$ do not
cover $\mathbb{E}^{3}$.

Consider an arbitrary lattice packing $\mathcal{F}^{\prime}$ of soft balls of
radii $1+\lambda$ that is ‘close’ to $\mathcal{F}$ sharing
$(1+\lambda)\mathbf{B}^{3}$ with $\mathcal{F}$. Then there is a smooth
deformation $\mathcal{F}(t)$, $t\in[0,1]$ such that
$\mathcal{F}(0)=\mathcal{F}$, $\mathcal{F}(1)=\mathcal{F}^{\prime}$, and for
every $t$ the length of the minimal lattice vector in $\mathcal{F}(t)$ is at
least $2$. Then the centers of the neighbors of $\mathbf{B}^{3}$ move on
smooth curves; that is, there are smooth curves
$\gamma_{i}(t):[0,1]\to\mathbb{E}^{3}$, $i=1,2,\ldots,12$ such that
$\gamma_{i}(0)$ is the center of $\mathbf{B}_{i}^{3}$. Recall that any lattice
packing of unit balls with each ball touched by $12$ others is an FCC lattice.
(See for example, [4].) Thus, without loss of generality one may assume that
$\mathcal{F}(t)$ is not congruent to $\mathcal{F}$ for any $0<t\leq 1$ and
therefore for some value of $i$,
$d^{\prime}_{i}:=\|\gamma_{i}(t)\|^{\prime}_{t=0}>0$.

Let the Dirichlet-Voronoi cell of $\mathbf{B}^{3}$ in $\mathcal{F}(t)$ be
denoted by $V(t)$. The soft density of $\mathcal{F}(t)$ is equal to
$\rho(\mathcal{F}(t))=\frac{\operatorname{vol}_{3}\left(V(t)\cap(1+\lambda)\mathbf{B}^{3}\right)}{\operatorname{vol}_{3}\left(V(t)\right)}$.
Let $F_{i}$ and $W_{i}$ denote, respectively, the face of $V$ touched by
$\mathbf{B}_{i}^{3}$, and $((1+\lambda)\mathbf{B}^{3})\cap F_{i}$. Note that
since the symmetry group of the FCC lattice acts transitively on the faces of
$V$, there are quantities $F$, $W$ such that $F=\operatorname{area}(F_{i})$
and $W=\operatorname{area}(W_{i})$ independently of the values of $i$.

As $\|\gamma_{i}(0)\|=2$ for every $i$, we have
$\operatorname{vol}_{3}(V)=\frac{1}{3}\sum_{i=1}^{12}\frac{1}{2}\|\gamma_{i}(0)\|\operatorname{area}(F_{i}))=4F$,
and $\operatorname{vol}_{3}\left(V\cap(1+\lambda)\mathbf{B}^{3}\right)>4W$.
Applying Theorem 5, we obtain that

$\left(\operatorname{vol}_{3}\left(V(t)\cap(1+\lambda)\mathbf{B}^{3}\right)\right)^{\prime}_{t=0}=\frac{1}{2}\sum_{i=1}^{12}d^{\prime}_{i}W.$

Similarly, we have

$\left(\operatorname{vol}_{3}\left(V(t)\right)\right)^{\prime}_{t=0}=\frac{1}{2}\sum_{i=1}^{12}d^{\prime}_{i}F.$

Thus, as $d^{\prime}_{i}\geq 0$ for all values of $i$, and $d^{\prime}_{i}>0$
for some values of $i$, it follows that

$\rho(\mathcal{F}(t))^{\prime}_{t=0}<\frac{2F\sum_{i=1}^{12}d^{\prime}_{i}W-2W\sum_{i=1}^{12}d^{\prime}_{i}F}{16F^{2}}=0.$

This completes the proof of Theorem 3.

## References

  * [1] F. Aurenhammer, R. Klein and D.-T. Lee, _Voronoi diagrams and Delaunay triangulations_ , World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2013.
  * [2] K. Bezdek and Z. Lángi, _Density bounds for outer parallel domains of unit ball packings_ , Proc. Steklov Inst. Math. 288/1 (2015), 209–225.
  * [3] K. Böröczky, _Closest packing and loosest covering of the space with balls_ , Studia Math. Sci. Hungar. 21 (1986), 79–89.
  * [4] K. Böröczky and L. Szabó, _12-neighbour packings of unit balls in $\mathbb{E}^{3}$_, Acta Math. Hungar. 146/2 (2015), 421–448.
  * [5] B. Csikós, _On the volume of the union of balls_ , Discrete Comput. Geom. 20 (1998), 449-461.
  * [6] H. Edelsbrunner and M. Iglesias-Ham, _On the optimality of the FCC lattice for soft sphere packing_ , SIAM J. Discrete Math. 32/1 (2018), 750–782.
  * [7] L. Fejes Tóth, _Some packing and covering theorems_ , Acta Sci. Math. (Szeged) 12 (1950), 62–67.
  * [8] T.C. Hales and S. McLaughlin, Sean, _The Dodecahedral Conjecture_ , J. Amer. Math. Soc. 23  (2010), 299–344.
  * [9] T. Lambert, _Empty shape triangulation algorithms_ , PhD thesis, University of Manitoba, 1994.
  * [10] J. Molnár, On the $\rho$-system of unit circles, _Ann. Univ. Sci. Budapest, Eötvös Sect. Math._ 20 (1977), 195–203.
  * [11] C.A. Rogers, _The closest packing of convex two-dimensional domains_ , Acta Math. 86 (1951), 309–321.
  * [12] C.A. Rogers, _Erratum to: The closest packing of convex two-dimensional domains, corrigendum_ , Acta Math. 104 (1960), 305-306.
  * [13] Ch. Zong, _The simultaneous packing and covering constants in the plane_ , Adv. Math. 218/3 (2008), 653–672.

Károly Bezdek
Department of Mathematics and Statistics, University of Calgary, Canada
Department of Mathematics, University of Pannonia, Veszprém, Hungary
E-mail<EMAIL_ADDRESS>

and

Zsolt Lángi
MTA-BME Morphodynamics Research Group
Department of Algebra and Geometry
Budapest University of Technology and Economics, Budapest, Hungary
<EMAIL_ADDRESS>