# Automatic Odometry-Less OpenDRIVE
Generation From Sparse Point Clouds

Leon Eisemann1 and Johannes Maucher2 *This publication was written in the
context of the AVEAS research project (www.aveas.org), funded by the German
Federal Ministry for Economic Affairs and Climate Action (BMWK) within the
program “New Vehicle and System Technologies”.1Leon Eisemann is with the
department of Artificial Intelligence & Big Data at Porsche Engineering Group
GmbH, 71287 Weissach, Germany2Johannes Maucher is with the Institute for
Applied Artificial Intelligence at Stuttgart Media University, 70569
Stuttgart, Germany

###### Abstract

High-resolution road representations are a key factor for the success of
(highly) automated driving functions. These representations, for example,
high-definition (HD) maps, contain accurate information on a multitude of
factors, among others: road geometry, lane information, and traffic signs.
Through the growing complexity and functionality of automated driving
functions, also the requirements on testing and evaluation grow continuously.
This leads to an increasing interest in virtual test drives for evaluation
purposes. As roads play a crucial role in traffic flow, accurate real-world
representations are needed, especially when deriving realistic driving
behavior data. This paper proposes a novel approach to generate realistic road
representations based solely on point cloud information, independent of the
LiDAR sensor, mounting position, and without the need for odometry data,
multi-sensor fusion, machine learning, or highly-accurate calibration. As the
primary use case is simulation, we use the OpenDRIVE format for evaluation.

##  I Introduction

The growing complexity of Advanced Driver Assistance Systems (ADAS) leads to
higher requirements for testing and evaluation of these systems. Especially
the functional safety and the safety of the intended functionality (SOTIF) of
(highly) automated driving (AD) functions must be ensured in a large number of
traffic situations. One possible method for the safety assessment is real-
world driving on public roads, with statistical validation[1]. The increasing
complexity implies the need for more and more kilometers driven for a
comprehensive evaluation. In [2], a statistical analysis shows that validation
by real test drives is infeasible for future automated functions. Based on the
average driven kilometers between two fatal accidents on German highways, the
authors derive that 6.61 billion kilometers are needed to encounter at least
one similar situation.

With these prerequisites, the adoption of simulation is critical to reduce
development time and ensure system robustness and reliability[3, 4].

For the extraction and simulation of a traffic scenario, the authors in [4]
identify three critical elements: a road representation, the traffic
participants, and the environment. A concept of the road is hereby considered
an integral part, as the structure and course of the road are one of the key
influential factors in the behavior of traffic participants. Albeit the
importance of road networks for evaluating driving functions, their creation
is still an open research topic.

In the field of simulation, extraction methods of respective representations
can be divided into four categories[5]:

First, high-definition (HD) maps or aerial images typically provide
information about the road network at a centimeter-level accuracy[3]. This
information can then be transformed into the respective format for simulation,
as shown in [3].

Second, the extraction and evaluation of road structures from a mobile mapping
platform. Mobile mapping platforms are vehicles fitted with a high number of
sensors, including Global Navigation Satellite System (GNSS), inertial
measurement unit (IMU), and light detection and ranging (LiDAR), which are
optimized to collect detailed environment representations[6][5].

Figure 1: General overview of our proposed method. We first build an overall
point cloud of the road, filter the respective line markings, generate the
respective lanes based on the markings, and in the last step, export into
OpenDRIVE. Hereby, the proposed method solely uses point cloud information and
exploits geometric properties of lane markings.

Third, the fusion of mobile mapping approaches and external data sources is
common to further reduce shortcomings of individual methodologies[5]. As shown
in [7], the authors thereby overcome the occlusion of LiDAR point clouds by
fusing the resulting road boundaries with satellite imagery.

Finally, maps created by service providers. Especially in automotive
simulation, these are commonly leveraged, for example, in [8, 9, 10]. However,
since these service providers operate commercially, there is hardly any
publicly available information about their methods and degree of automation.
Furthermore, these come with additional costs, coordination, and planning
efforts. For this reason, they are considered out of scope in the context of
this work.

TABLE I: Comparison of the prerequisites of previous research and the
resulting length of reconstruction. If not explicitly stated, it is derived
from the evaluation and graphics shown. In comparison, our methodology needs
the fewest prerequisites in terms of sensors used and mounting positions, can
reconstruct other traffic participants, and achieves the longest
reconstruction.

Authors | nr. sensors | hor. FoV | mounting pos. | rec. traffic | odometry needed | reconstruction length
---|---|---|---|---|---|---
Haala et al.[11] | 4 | 360° | mult. + ground facing | no | GNSS + IMU | 1,500 m
Ibrahim et al.[12] | 1 | 360° | top | no | no | 3,600 m
Yang et al.[13] | 2 | 360° | mult. | no | no | 2,200 m
Chiang et al.[14] | 1 | 360° | ground facing | no | GNSS + IMU | 400 m
Karunakaran et al.[15] | 7 | 360° | mult. + ground facing | yes | IMU | 200 m
Ours | 1 | 82° | front | yes | opt. | 14,000 m

The requirements for the creation of road representations depend on the use
case. We deemed none of the above-mentioned feasible for use in automotive
simulation. In application, map or aerial-based methods have been shown to be
inaccurate and often not up to date, especially in the case of road works.
Road works have special importance for the safety assessment of automated
driving functions, as [16] has shown that the presence of a work zone is
likely to increase the crash rate.

Therefore, the creation of road models through a mobile mapping platform is
more flexible. However, this flexibility often depends on very specific sensor
setups and mounting points. This leads to high costs for equipment, sensors,
and workforce and hinders the broad availability of these platforms. Also,
these vehicles are often unable to record traffic participants, resulting in
two separate recording drives or vehicles. In the case of additional drives,
there is no guarantee that the course of the road is unchanged. Furthermore,
recent research [12, 13, 14, 15] has shown to be reliant on specific sensor
types, e.g., line-wise scanners, sensor characteristics, like 360° field of
view (FoV), or mounting points, which makes the adoption on other data sources
complex.

To solve some of the mentioned disadvantages, we propose a generic approach
capable of producing a standardized map format. This is achieved in an
automated manner, without using odometry or any prior knowledge about the
road. We use a sparse LiDAR point cloud derived directly from real-world test
drives of cut-in scenarios.

In the evaluation, we compare our results quantitatively to other map sources
and show the quality through a trajectory-based simulation of the original
test drive. As a map standard, we adopt OpenDRIVE, which is further explained
in Sec. II-B, where we contribute to the creation from real-world measurement
data. We propose a distance-based look ahead / back geometry fitting to solve
geometric leap and kink problems described in [17].

The paper is structured as follows: Sec. II provides the motivation and a
brief overview of prior research. Sec. III presents the data used and applies
the proposed method to highway scenarios. Finally, Sec. IV evaluates the
results and gives an outlook on limitations and avenues for future research.

##  II Background

The following section reviews 3D point cloud mapping approaches and introduces
the map standard used in this work.

###  II-A Related Work

For constructing the road networks of the city center of Stuttgart, Germany,
with an area of 1.5 km x 2 km, the presented study in [11] uses a mobile
mapping platform with 360° scanner FoV and GNSS. The results show the
possibility to create a point cloud-based representation of city areas with
high accuracy.

In [12], data is collected by driving circles around city blocks. The LiDAR
scans of each block are then processed, including subsampling, noise removal,
deduplication, and smoothing. This approach creates a merged point cloud for
the Central Business District of Perth, Australia.

Leveraging curb points, [13] proposes the extraction of road models based on
point clouds from a 360° FoV multi-LiDAR setup. In the described process, a
sliding window approach is adapted to filter non-ground points and curb points
in every scan line. Individual points are tracked and refined, allowing global
consistency to be preserved.

An automated approach exporting OpenDRIVE is presented in [14], using the
trajectory of the ego vehicle and a ground-facing laser scanner. A multistage
reconstruction process is used to recreate the road network based on extracted
road edges, line marking classification, and the trajectory. Compared to other
methods, the authors can also classify road segments into lane lines, stop
lines, arrows, and others.

The methods mentioned above focus on the sole generation of road
representations. As stated in Sec. I, this would result in separate recordings
for the road and traffic participants, which yields several disadvantages.
First, referencing the same map coordinate system while compensating for the
inaccuracy of GNSS and tracking algorithms or systems. Second, based on the
time difference between recordings, the course of the road can be changed,
e.g., through construction sides or accidents. These two main factors render
these approaches labor-intensive and uncertain for reliable usage in AD
simulation or traffic behavior analysis.

A higher focus on traffic behaviour is shown in [15]. In addition to a road
model, the authors are able to derive and analyse traffic participants. The
authors propose a fully automated point cloud-based system generating
OpenDRIVE and OpenSCENARIO [18] from a single recording. Data is sourced from
a vehicle fitted with six LiDAR sensors and an additional LiDAR facing the
ground. Based on tracking information, they separate between dynamic and
static objects, sort the static point cloud in reference to the ego vehicles
odometry. Through the exploitation of the line-wise LiDAR scanning pattern,
lane markings are filtered. These are then transformed into the Lanelet2 [19]
format, which is again converted into OpenDRIVE. Although this work focuses on
the driving scenario extraction and the resulting road is not evaluated, it
can be assumed that they can reconstruct several hundred meters based on the
extracted scenarios.

The preconditions of the presented methods and ours are compared in Tab. I.
The need for 360° FoV, the reliance on special sensor characteristics,
mounting positions, and highly accurate odometry information hinder the
adaption of these methodologies without the concrete vehicle at hand. Our
motivation is to achieve precise road models, without leveraging sensor
specifications, a vast number of sensors, and without the need for highly-
accurate calibration, multi-sensor fusion, or machine learning. In addition,
we aim for direct creation from test drives and independence from odometry
information. The later allows the use of different LiDAR sources, e.g.,
multiple vehicles, drones, and static sensors.

###  II-B Map Format

In [14], the authors extensively compare different formats for HD map
creation, e.g., Autoware Vector Map, OpenDRIVE, Lanelet2, and Navigation Data
Standard. Based on their evaluation and our focus on automotive simulation,
OpenDRIVE is selected as HD map format. One of the main reasons is the wide
adoption in the automotive industry and support by tools and software
platforms for creating, editing, and using road data in simulation and testing
scenarios [14]. OpenDRIVE originates from the automotive industry’s efforts
for standardization and provides a comprehensive and flexible framework for
describing the geometry, topology, and attributes of roads[20].

The standard defines the overall course of the road along a reference line.
Further elements, e.g., elevation and lanes, are then attached to it. Per
definition, a reference line can consist of four types of geometries, namely
line, spiral, arc, or paramPoly3 (parametric cubic curve). These geometries
are usually concatenated to describe a more detailed or longer road
structure[20].

##  III Method

Similar to other approaches, we also adopt LiDAR data as input. Over the last
few years, the costs for LiDAR sensors dropped significantly, which
facilitates their use in research. They provide high positional accuracy of
detections, and the measured reflectivity or intensity allows easier
recognition of line markings. In contrast to previously mentioned methods, see
Tab. I, we do not use a high-resolution LiDAR, a special mounting position, or
a 360° FoV, and instead, use a single front-mounted LiDAR sensor with an 82°
horizontal FoV. In the following section, we present our proposed method. For
better comprehension, individual steps are summarized as pseudocode, and
functions are marked in italics in the text.

###  III-A Data & Preprocessing

As data collection vehicle, we make use of the JUPITER platform as described
in [21]. The platform consists of a Porsche Cayenne fitted with multiple Livox
LiDARs and GeneSys ADMA GNSS inertial system. To show our approach’s
robustness, we exclusively use the front-mounted LiDAR. This sensor features a
complex inhomogeneous scanning pattern, which shows our approach’s
independence of sensor characteristics. Compared to other methods, the data
collection was not focused on road generation but on the acquisition of
dynamic driving behavior and critical driving scenarios as part of the AVEAS
111www.aveas.org [22] research project. To derive realistic traffic behavior,
data was collected mainly on the German interstate highways A8 and A81 around
Stuttgart at peak traffic times. The speed profile of the recordings ranges
from 80 to 140 km/h in the considered parts. We extract the data between the
highway’s entry and exit, with the entry as the origin of our world coordinate
system. The world coordinate system is defined in the 3D Euclidean space and
is axis-aligned with the geodesic coordinates.

We convert each LiDAR scan into a point cloud with X, Y, Z, Reflectivity for
every detection. Resulting point clouds are stored in the vehicle coordinate
system as defined in [23]. The corresponding GNSS coordinates are stored
separately.

Algorithm 1: Calculation of Candidate Lines

1:clusters.append(DBSCAN(point cloud))

2:if cluster.length $\geq$ threshold then

3: clusters.append(SplitCluster(cluster))

4:end if

5:cCenters.append(CalcCenterBB(cluster)) $\triangleright$ parallel

6:dirVecs.append(LineRANSAC(cluster)) $\triangleright$ parallel

7:dirVecs $=$ UnifyDirection(dirVecs)) $\triangleright$ parallel

8:for cluster in clusters do

9: if currentLine $\geq$ 2 then

10: dirVec $=$ Eq. (1)

11: end if

12: candidates.append(SearchMark(cCenters, dirVec))

13:end for

14:while $connection$ do

15: candid $\leftarrow$ candidates

16: if Intersec(candid.end, candidates.start) then

17: candid $=$ Combine(candid, intersec)

18: candid $=$ DistSort(candid)

19: candidates.append(candid)

20: connection $=$ True

21: end if

22:end while

23:return candidates

24:$\triangleright$ Overview over the lane generation process. Function names
are used for visibility and are further explained in Sec. III-C and Sec. III-D

###  III-B Line Marking Extraction

Since the following steps of our method use point cloud data of line markings
as a representation, we showcase the extraction of these.

As data source, we use the LiDAR point clouds directly in the vehicle
coordinate system for ground plane estimation. For outlier reduction, the
point clouds are first cropped to the maximum sensor range specified by the
manufacturer. From this, only points below the mounting position of the sensor
are considered. This reduces the number of points originating from
surroundings, e.g., traffic signs or bridges, and allows a more robust ground
plane estimation. Then, through a RANSAC[24]-based approach, we estimate the
ground plane and artificially raise it by a margin of 15 cm to account for
possible road normal curvatures. The value of 15 cm is hereby chosen, as it
corresponds to the average height of curbstones in Europe. Lane markings are
filtered through their high reflectivity in the LiDAR returns. Based on
evaluations on our dataset, we choose an reflectivity of 50 % as filter
threshold. While the measured reflectivity of the sensor under use is
estimated through a Lambertian reflectance model, the interpretation and
calculation depend on the sensor used, and likely would have to be adjusted
for new data.

The extracted lane markings are accumulated and translated to their respective
position in the world coordinate system, based on GNSS as shown in Fig. 1.
Although we use the GNSS-derived translation, one could also derive the
translation based on, e.g., a SLAM- or ICP-based approach as in [25, 26].
Independently from the translation, reflectivity-based filtering leads to
considerable outliers through multipath reflections and other environmental
impacts. Therefore, an additional radius-based outlier reduction is done.
Based on different evaluations on our data, we remove each point with less
than four neighboring points in a half-meter radius.

###  III-C Generation of Lane Marking

Figure 2: Overview over lane generation and positional calculation. Lane
marking point clouds are displayed in blue, and respective estimated centers
in orange. The directional vectors calculated by Eq. 1 are shown in shades of
green and derived normal-vectors in red. The resulting reference line is
displayed in purple.

The overall generation of candidate lane markings is listed in Alg. III-A for
better comprehension.

As our method depends on the individual lane markings’ geometry, we first
cluster points that belong to each lane mark. Due to the fact, that the total
number of markings is unknown at this stage of the process, we adopt DBSCAN
[27] clustering.

Analyses of the resulting clusters indicate that depending on the ego position
on the road, clusters of solid lane markings can reach up to more than 1 km in
length. These continuous markings are valuable for lane generation since they
contain dense information about the course of the road, also in-between dashed
markings. To integrate this information into the further process and achieve a
unified method, markings reaching over 30 m in length are divided into
uniformly sized slices; see Alg. III-A line 2. The resulting slices are 6
meters long, which equals the standard size of dashed markings on German
highways [28].

The reconstruction of lane geometries in point cloud data is a non-trivial
task. Through the nature of point clouds, methods like nearest neighbor would
yield wrong connections between lanes. Hence, for the construction of the
lanes, related research, e.g., [15, 14], integrates ego trajectory information
to solve this limitation, which in return requires an accurate GNSS and/or IMU
setup.

To be able to reconstruct the lanes without the use of ego information, we
exploit the geometric properties of the individual lane markings. The
underlying assumption is that clusters derived from dashed as well as solid
lane markings are elongated in the direction of the road[28]. Therefrom, we
evaluate the direction of each cluster through a RANSAC-based line
calculation, see LineRANSAC, to derive a directional vector $\hat{v}^{*}$ for
each line marking. Since our approach deliberately avoids the direct
utilization of a driving direction, and RANSAC may return both positive or
negative directional vectors for the symmetric lane marks, we subsequently
unify them based on the directional vector between the origin of the
coordinate system and the cluster centers in Alg. III-A as UnifyDirection.

To achieve a stable connection between markings, calculations leverage full 3D
point cloud information. In addition, this also reduces the chances of
interferences through high-reflectivity outliers still contained in the point
cloud and, thus, also lowers the quality requirements of the previous steps. A
search along the directional vector is executed from the cluster closest to
the origin.

Since the directional vector $\hat{v}^{*}$ can contain a high variation and
inaccuracies through partial scans or alignment issues, we calculate any
further vector $\hat{v}$ based on Eq. (1) with $\gamma=0.5$, to provide
additional stability:

$\hat{v}_{\text{i+1}}=\gamma\cdot\hat{v}^{*}_{\text{i}}+(1-\gamma)\cdot\hat{v}^{*}_{\text{i-1}}$
(1)

As shown in Alg. III-A and Fig. 2, SearchMark iteratively calculates the next
expected mark center $p_{\text{c}}$ based on the distance $d$, through
$p_{\text{c}}=\hat{v}\cdot d$, where a ball radius search for the next center
point is done. The overall search is executed in three-meter steps for a total
length of 27 m, which is 1.5$\times$distance between the center of each line
marking on German highways [28]. Through the high upper limit and step-wise
procedure, we expect our method to work in other countries as well. The ball
radius search is executed with a radius of 1.75 m, which was chosen as it
equals half of the minimum lane width [28]. If a point is found, it is added
to the stack, and an additional point-to-line-segment calculation is done to
add missed clusters. The process is repeated as long as cluster centers are
found for the current line. Resulting candidate lines are assigned a random ID
for further processing.

Algorithm 2: Calculation of reference line

1:normVecs $=$ CalcNormVec(candidates)

2:for normVec in normVecs do

3: if Intersec(normVec, candidates) then

4: dist $=$ dist(normVec.start, intersec.point)

5: dist $=$ dist % 3.0m

6: lookupRel.append(laneID, intersecSide, dist)

7: end if

8: relativeLookups $\leftarrow$ lookupRel

9:end for

10:for lookup in relativeLookups do

11: if lookup in globalLookup then

12: globalLookup.append(lookup.allIDs)

13: end if

14:end for

15:return globalLookup

16:$\triangleright$ Overview over the lane generation process. Function names
are used for visibility and explained in Sec. III-E

###  III-D Combining Candidate lines

Since outliers are reduced through the generation of the candidates, higher
tolerances can be used for the combination of candidates. As the correct order
of the markings is needed, the previously generated candidate lines are sorted
by closest point sampling starting from the origin, in Alg. III-A as DistSort.
On this basis, another point-to-line-segment check is executed to combine
candidates which starting or end point is located between another candidate
segment. An additional search is done to achieve a more stable connection
between the candidates and higher stability against occlusion, similar to the
previous steps. This is done from the end point of every candidate for a total
of 63 meters. If a matching candidate is found, the search candidate’s ID is
assigned by Combine, and the resulting line is sorted again. This whole
process repeats until no new combination is found.

###  III-E Calculation of Reference Line

Figure 3: Calculation of the GlobalLookup, as described in Sec. III-E. The
relative position is sorted through line ids in the relative positional
lookups.

Since our method does not rely on the ego vehicle’s odometry, we estimate the
number of lanes based on the relative position between lane markings. These
relative lookups are then solved to a global relation, as shown in Alg. III-C.

In the first step, we transfer the calculated lanes into 2D space by simply
omitting the Z-dimension for the calculation. To evaluate the position of the
lanes relative to each other, we first calculate the normal vectors $n$ for
each line segment between cluster centers. Through leveraging the directional
unification, we calculate the normals left and right of the segments in
CalcNormVec. The relative position of each lane is then estimated by the line
intersection between the normals and every segment of candidates, as shown in
Fig. 2. Additionally, the distance of the intersection towards the candidate
line segment is evaluated and used for estimating the lane widths based on
governmental regulations. For each lane, the resulting intersections and
distances are saved in RelativeLookup, as described in Alg. III-C. These
lookups are combined based on similar line ids into a GlobalLookup, as shown
in Fig. 3. For example, if a lane with ID 3 has ID 5 to the right and another
lane with ID 7 is intersected left from ID 5, then it can be concluded that
both lane ID 3 and ID 7 are partial scans of the same lane.

In doing so, we achieve what we call superlines, which contain each
candidate’s global positional lane offset.

This process yields the number and width of lanes, from which we calculate the
road’s centerline. Based on the width of the road and the known relative
offset of each lane, the normal vector towards the center of the road is
calculated, and a new point is created with X, Y-coordinates. To keep the
height information of the road, the original Z-information of the candidate
lines is added. This process is done for every line marking center in each
superline, which results in a high resolution reference line, see refLine.

###  III-F Export of OpenDRIVE

Algorithm 3: Calculation of OpenDRIVE

1:segments $=$ SplitByDist(refLine)

2:for seg in segments do

3: geo.segRotation $=$ EvalRot(seg)

4: lookAhead $=$ CalcDist(seg.end, refLine)

5: lookBack $=$ CalcDist(seg.start, refLine)

6: seg $=$ CompensateRot(seg, geo.segRotation)

7: p $=$ NormalizeDist(seg, lookBack, lookAhead)

8: geo.paramPolyU $=$ WeightedFit(p.x)

9: geo.paramPolyV $=$ WeightedFit(p.y)

10: geo.paramPolyZ $=$ Fit(seg.z)

11: add geo to OpenDRIVE planView

12:end for

13:$\triangleright$ Overview of the OpenDRIVE generation. Function names are
used for visibility and are further explained in Sec. III-F

As the re-calculation and direct export of measurement data into OpenDRIVE is
a nontrivial task, it is outlined in more detail. The overall steps are
displayed in Alg. III-F.

The OpenDRIVE standard recommends using parametric cubic curves to generate
complex geometries from measurement data[20]. The amount of information that
can be displayed in one curve is limited by their cubic nature. To circumvent
this limitation, we split the calculated continuous reference line into 100 m
long segments for the export. As presented in Alg. III-F, this is done through
the SplitByDist function. Important in this context is that the overall
continuity of the road model has to be preserved, despite the segmentation.
This is especially important for the usage in AD development. As described in
[17], geometric leaps or kinks can cause vehicle dynamic models to fail.
Primarily through offsets in the extracted lane marks and therefrom derived
reference line, geometric leaps and kinks are of particular interest.

To prevent these and allow a smooth transition between geometric elements, we
introduce a distance based look ahead and look back index. These indexes
contain parts of the predecessor, respectively successor segment, used for
curve fitting but are not part of the final geometry. From different
evaluations on our data, we defined the size for these lookups as 1/8 of the
segment length.

Geometric elements consist of a local Cartesian coordinate system U, V, which
is placed in the inertial X, Y coordinate system, see [20]. For the correct
placement in the inertial system, each element is rotated by a heading
parameter. To estimate this parameter, the mean of all marking centers in the
segment is evaluated, and the angle towards the X-axis is derived. The line
segment is then compensated by the negative heading to achieve the U, V
coordinate system for estimating the curve parameters.

Curve fitting for ParamPolyU and ParamPolyV integrates the look ahead and look
back index to prevent the previously mentioned geometric kinks and leaps.

Additionally to the indexes, we use a weighting of the first and last original
lane marking for the fitting of the U, V cubic curves. Combined with the
extended indexes, this prevents most geometric offsets, as through the look
ahead and back indexes, the successor and predecessor shapes are integrated
into the curves’ fit, and the weighting prevents leaps. Calculated parameters
are then saved in the geometric object with the previously derived centered X,
Y-coordinates and heading.

Road elevation is defined as an additional element along the calculated road
geometry and is calculated directly from the original reference markers,
omitting weighting and look ahead and look back indexes.

The calculation of super-elevation is done in the same manner. The rotation of
the road surface is hereby derived from the calculated ground plane in Sec.
III-B.

(a) 1

(b) 1

(c) 1

Figure 4: Example excerpts of one full drive for qualitative comparison. The
respective camera frame and LiDAR scan from the original recording are
referenced in each image. The resulting OpenDRIVE is displayed as esmini [29]
rendering, including traffic participants from generated OpenSCENARIO[18].

##  IV Result and Discussion

The state-of-the-art methods presented in Tab. I can reconstruct several
hundred meters of road. In comparison, our method can successfully handle and
reconstruct several kilometers of highway, as shown in Fig. 4.

###  IV-A Quantitative Analysis

TABLE II: Evaluations of our resulting OpenDRIVE maps. For accuracy we compare against PEGASUS [30] HD maps and for reproducibility against our methodology. | agst. PEGASUS HD | agst. self (ours)
---|---|---
RMSE | 0.303 (m) | 0.24 (m)
avg. distance | 0.238 (m) | 0.20 (m)
std. derivation $\sigma$ | 0.187 (m) | 0.13 (m)
eval. length | 44.8 (km) | 30.6 (km)

The quantitative evaluation of map data depends on the relevant purpose and
parameters, including the format or standard used, and is an ongoing research
topic. The OpenDRIVE standard provides flexibility to express road layouts in
different ways, leading to equivalence classes of roads of identical or near-
identical physical layouts but considerably different parameters, thereby
challenging the comparison of road models. For example, the relative position
of reference line, lanes, and georeference can be offset at multiple
occasions.

Therefore, comparisons are performed on the resulting geometries of the
considered OpenDRIVE maps rather than the parameters describing them. We note
that within a local neighborhood, only lateral errors are measurable, with
considered OpenDRIVE features being translation-invariant along the reference
line except for locations where the lateral layout changes. Individual road
marking locations, for example, are not mandatory in OpenDRIVE and are not
included in the references since they can frequently change in practice due to
road works.

Hence, we calculate a parametrization-invariant lateral distance between the
roads through the global position of the reference lines in the reference map
and ours. Comparison is made by sampling uniformly spaced points from each
reference line. Between both lines, the nearest neighbors and the distance
between them are calculated. Similar to [14], we evaluated the Root Mean
Square Error (RMSE), average distance, and standard deviation ($\sigma$).

As the methodologies presented in Tab. I are vehicle-dependent, we evaluate
against HD maps from the PEGASUS research project [30]. As input data, we use
four different recordings, taken over the course of 8 weeks, following the
same part of the German highway A8. The drives contain a total of 44.8 km
recorded, including 31 cut-in scenarios and 29 ego vehicle lane changes, with
an average speed of 116 km/h. Recording conditions range from sunny to light
rain, with mid to high traffic volume, with speed profiles from 80 to 140
km/h.

Comparing the resulting 44.8 km reconstruction against PEGASUS HD maps yields
an average distance of 0.238 m, an $\sigma$ of 0.187 m, and an RMSE of 0.303
m. According to the Taiwan HD map standards [31], the 3D map accuracy should
be lower than 30 cm. As shown in Tab. II, the results of our proposed
methodology satisfy these requirements.

A different reference is the reproducibility of results in repeated drives
under different conditions described above. Thus, we choose one recording
randomly as a reference map and evaluate the remaining three against it. We
achieve a combined average distance of 0.20 m, with an $\sigma$ of 0.13 m and
RMSE of 0.24 m. The measured offsets hereby originate from a multitude of
factors. As initially stated, we only introduce moderate requirements on
calibration and accuracy. Hence calibration offsets and GNSS offsets affect
the results as well as the alignment of geo-references, and the curve fitting
of the reference line. Despite these offsets, the results show that our
proposed method achieves reproducible maps across different traffic and
driving situations.

Regarding the estimated lane numbers, our approach reconstructs a total number
of three lanes along the highway section, which is consistent with the true
number of lanes, disregarding entry and exit lanes.

To provide a metric for the lateral accuracy of our approach, we evaluate the
estimated lane width from Sec. III-E. Therefore, the two most left lanes are
used, as these have similar lane width. Evaluated over the total of 44.8 km,
our method yields an average lane width of 3.56 m, with an $\sigma$ of 0.22 m.
Governmental regulations stipulate a lane width of 3.5 m with a dashed marker
width of 0.15 m and 0.30 m for solid marks on the left road boundary[28].

###  IV-B Qualitative Analysis

For the qualitative analysis, we generate an additional OpenSCENARIO [18] file
and reference it to the OpenDRIVE. For the object detection of the traffic
participants, we use the series sensors.

Figure 4 demonstrates a set of frames from the corresponding esmini [29]
rendering. The full video is available on our data exchange
222https://dataexchange.porsche-
engineering.de/wl/?id=wiMyDDwFZUnb1CUokIuchMGuLnfgPuYy
Password: IEEE-ITSC23. The examples demonstrate the correct placement of the
ego vehicle, as well as other traffic participants. Even in complex situations
with a high number of vehicles, the generated road representation shows a
close-to-real shape, with observed manoeuvrers, such as cut-in and cut-out,
replicated correctly in the simulation. This is also achieved in cases where
the ego vehicle executes a lane change or is on a non-center lane.
Furthermore, not only the position on the lane shows high accuracy, but also
the position within each lane. For example, in Fig. LABEL:fig:qual-examples-2,
LABEL:fig:qual-examples-3, the target vehicle is on the far right and left
side of the lane, respectively, which is also closely reconstructed in the
simulation.

As described, all vehicles in the simulation are placed in reference to the
GNSS with an accuracy of $\pm$5 cm. Hereby we conclude that the road has a
high degree of realism. Even in situations where the GNSS has a higher offset,
e.g., through loss of GNSS signal, our method can correctly infer the road
structure and display a smooth and homogeneous transition between geometric
elements.

##  V Conclusion and Future Work

Based on the importance of road networks for the evaluation of (highly)
automated driving functions, research on their creation has seen considerable
interest over the last few years.

In this paper, we proposed an algorithm that can automatically generate high-
resolution road representations directly from real-world test drives.
Leveraging sparse LiDAR data, the algorithm involves lane marking extraction,
3D lane line generation, and direct export into OpenDRIVE standard. Without
relying on the prior road or odometry information, the algorithm is
independent of the LiDAR sensor and allows accumulation from multiple sources.
Furthermore, the algorithm’s results fulfill the requirements for HD map
standards and driving function simulation, which could be shown through
quantitative and qualitative metrics. Simulated test drives show the accurate
placement of traffic participants close to reality, even at ego lane changes.

Entry or exit lanes represent avenues for further research. We successfully
integrated a classification in different tests by leveraging the distance
between lane markings. As these are normally different from straight lanes, we
were able to integrate them into the OpenDRIVE. Although, problems arise when
the ego vehicle only partly records these special lanes. Similar situations
currently occur with adaptively rising or lowering lane numbers. Another point
of interest for future research is the adaption of different sensors. As our
method, by Sec. III-B, only relies on a 2D or 3D representation of line
markers, an adaption onto other sensors technologies, like cameras, is
expected to be possible.

## References

  * [1] D. Karunakaran, S. Worrall, and E. Nebot, “Efficient falsification approach for autonomous vehicle validation using a parameter optimisation technique based on reinforcement learning,” 2020. [Online]. Available: http://arxiv.org/abs/2011.07699
  * [2] W. Wachenfeld and H. Winner, _The Release of Autonomous Vehicles_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016, pp. 425–449.
  * [3] S.-W. Park, K. Patil, W. Wilson, M. Corless, G. Choi, and P. Adam, “Creating driving scenarios from recorded vehicle data for validating lane centering system in highway traffic,” _The MathWorks, Inc., General Motors_ , 2020.
  * [4] Z. Xinxin, L. Fei, and W. Xiangbin, “CSG: Critical scenario generation from real traffic accidents,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_ , 2020, pp. 1330–1336, ISSN: 2642-7214.
  * [5] Z. Bao, S. Hossain, H. Lang, and X. Lin, “High-definition map generation technologies for autonomous driving,” 2022. [Online]. Available: http://arxiv.org/abs/2206.05400
  * [6] Á. Barsi, A. Csepinszky, J. M. Lógó, N. Krausz, and V. Potó, “The role of maps in autonomous driving simulations,” in _Periodica Polytechnica Transportation Engineering_ , vol. 48, no. 4, 2020, pp. 363–368. [Online]. Available: https://pp.bme.hu/tr/article/view/15852
  * [7] L. Ma, Y. Li, J. Li, J. M. Junior, W. N. Gonçalves, and M. A. Chapman, “BoundaryNet: Extraction and completion of road boundaries with deep learning using mobile laser scanning point clouds and satellite imagery,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, 2022.
  * [8] F. Montanari, C. Stadler, J. Sichermann, R. German, and A. Djanatliev, “Maneuver based resimulation of driving scenarios based on real driving data,” in _2021 IEEE Intelligent Vehicles Symposium (IV)_ , 2021, pp. 1124–1131.
  * [9] A. Richter and M. Scholz, “Systematische und effiziente erhebung hochgenauer straßengeodaten für geoinformationssysteme und fahrsimulationen,” in _INFORMATIK 2016 - 14. Workshop Automotive Software Engineering_ , ser. Lecture Notes in Informatics (LNI) - Proceedings, H. C. Mayr and M. Pinzger, Eds., vol. P-259. Köllen Druck+Verlag GmbH, Bonn, 2016, pp. 1579–1589.
  * [10] B. Schwab, C. Beil, and T. H. Kolbe, “Spatio-semantic road space modeling for vehicle–pedestrian simulation to test automated driving systems,” in _Sustainability_ , vol. 12, no. 9, 2020, p. 3799.
  * [11] N. Haala, M. Peter, J. Kremer, and G. Hunter, “Mobile LiDAR mapping for 3d point cloud collection in urban areas—a performance test,” _Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci_ , vol. 37, 2008.
  * [12] M. Ibrahim, N. Akhtar, M. A. A. K. Jalwana, M. Wise, and A. Mian, “High definition LiDAR mapping of perth CBD,” in _2021 Digital Image Computing: Techniques and Applications (DICTA)_ , 2021, pp. 01–08.
  * [13] B. Yang, L. Fang, and J. Li, “Semi-automated extraction and delineation of 3d roads of street scene from mobile laser scanning point clouds,” _ISPRS Journal of Photogrammetry and Remote Sensing_ , vol. 79, pp. 80–93, 2013.
  * [14] K.-W. Chiang, H.-Y. Pai, J.-C. Zeng, M.-L. Tsai, and N. El-Sheimy, “Automated Modeling of Road Networks for High-Definition Maps in OpenDRIVE Format Using Mobile Mapping Measurements,” _Geomatics_ , vol. 2, no. 2, pp. 221–235, Jun. 2022.
  * [15] D. Karunakaran, J. S. Berrio, S. Worrall, and E. Nebot, “Automatic lane change scenario extraction and generation of scenarios in OpenX format from real-world data,” arXiv, Tech. Rep. arXiv:2203.07521, Mar. 2022. [Online]. Available: http://arxiv.org/abs/2203.07521
  * [16] H. Yang, K. Ozbay, O. Ozturk, and K. Xie, “Work zone safety analysis and modeling: A state-of-the-art review,” _Traffic Injury Prevention_ , vol. 16, no. 4, pp. 387–396, 2015, pMID: 25133956. [Online]. Available: https://doi.org/10.1080/15389588.2014.948615
  * [17] B. Schwab and T. H. Kolbe, “Validation of parametric OpenDRIVE road space models,” in _ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences_ , vol. X-4/W2-2022, 2022.
  * [18] Association for Standardization of Automation and Measuring Systems e.V. ASAM OpenSCENARIO . [Online]. Available: https://www.asam.net/standards/detail/openscenario/
  * [19] F. Poggenhans, J.-H. Pauls, J. Janosovits, S. Orf, M. Naumann, F. Kuhnt, and M. Mayr, “Lanelet2: A high-definition map framework for the future of automated driving,” in _Proc. IEEE Intell. Trans. Syst. Conf._ , Hawaii, USA, November 2018.
  * [20] Association for Standardization of Automation and Measuring Systems e.V. ASAM OpenDRIVE. [Online]. Available: https://www.asam.net/standards/detail/opendrive/
  * [21] J. Haselberger, M. Pelzer, B. Schick, and S. Müller, “Jupiter – ros based vehicle platform for autonomous driving research,” in _2022 IEEE International Symposium on Robotic and Sensors Environments (ROSE)_ , 2022, pp. 1–8.
  * [22] L. Eisemann, M. Fehling-Kaschek, H. Gommel, D. Hermann, M. Klemp, M. Lauer, B. Lickert, F. Luettner, R. Moss, N. Neis, M. Pohle, S. Romanski, D. Stadler, A. Stolz, J. Ziehn, and J. Zhou, “An approach to systematic data acquisition and data-driven simulation for the safety testing of automated driving functions,” in _26th IEEE International Conference on Intelligent Transportation Systems ITSC 2023_ , 2023.
  * [23] International Organization for Standardization, “ISO 8855:2011 Road vehicles — Vehicle dynamics and road-holding ability,” Dec. 2011. [Online]. Available: https://www.iso.org/standard/51180.html
  * [24] M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” _Commun. ACM_ , vol. 24, no. 6, p. 381–395, jun 1981. [Online]. Available: https://doi.org/10.1145/358669.358692
  * [25] Livox, “Horizon Highway SLAM,” Mar. 2023. [Online]. Available: https://github.com/Livox-SDK/horizon_highway_slam
  * [26] I. Vizzo, T. Guadagnino, B. Mersch, L. Wiesmann, J. Behley, and C. Stachniss, “KISS-ICP: In Defense of Point-to-Point ICP – Simple, Accurate, and Robust Registration If Done the Right Way,” _arXiv prepr._ , 2022. [Online]. Available: https://arxiv.org/pdf/2209.15397.pdf
  * [27] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in _Proceedings of the Second International Conference on Knowledge Discovery and Data Mining_ , ser. KDD’96. AAAI Press, 1996.
  * [28] H. Frank and H. Reinsberg, “Leitfaden Fahrbahnmarkierung,” in _Schriftenreihe Verkehrssicherheit_. Deutsche Verkehrssicherheitsrat (DVR), Deutsche Studiengesellschaft für Straßenmarkierungen (DSGS), 2017.
  * [29] esmini, “Environment Simulator Minimalistic (esmini),” Jan. 2023, original-date: 2019-05-03T07:49:16Z. [Online]. Available: https://github.com/esmini/esmini
  * [30] PEGASUS research project. [Online]. Available: https://www.pegasusprojekt.de/en/about-PEGASUS
  * [31] High Definition Maps Research Center, Taiwan Telematics Industry Association: Taipei City, “Hd maps data contents and formats standard v1.1,” 2020.


$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ receives

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{i,3,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1366}&{\color[rgb]{0.56640625,0.07421875,0.99609375}482}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1635}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1264}&{\color[rgb]{0.4921875,0.828125,0.12890625}306}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ receives

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{i,4,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1115}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1779}&{\color[rgb]{0.2890625,0.56640625,0.88671875}656}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1854}&{\color[rgb]{0.4921875,0.828125,0.12890625}994}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ receives

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{i,5,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1911}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1008}&{\color[rgb]{0.2890625,0.56640625,0.88671875}434}&{\color[rgb]{0.81640625,0.0078125,0.10546875}357}&{\color[rgb]{0.4921875,0.828125,0.12890625}1604}\\\
\end{bmatrix}^{\intercal}}\end{array}.$

According to Algorithm 5, $D_{4}=1772$ is generated.

We compute $P_{4}^{n-2}=510$, and then deduct that

$D_{4}\neq P_{4}^{n-2}\implies p_{0,4}=1$

| $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$
---|---|---|---|---|---|---|---|---
$p_{1}=143$ | 1 |  | 0 |  |  0 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{2}=124$ | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |  |  0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{3}=217$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ |  |  $\Lsh$ |  |  $\Lsh$ |  |  $\Lsh$ |
$p_{4}=222$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ |  |  $\Lsh$ |  |  $\Lsh$ |  |  $\Lsh$ |
$p_{5}=86$ | 0 |  | 1 |  | 0 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$\left[~{}p_{0}~{}\right]_{\text{base 2}}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 |  | 1 |  | 0 |  | 1 |  |  |  |  |  |  |  |

Table 11: Two or more bidders for $j=4$

For $j=5$, Algorithm 4 generates $B_{5}=454$ and $P_{5}=2025$. $K_{1,5}\neq
B_{5}$, $K_{2,5}\neq B_{5}$, $K_{3,5}\neq B_{5}$, $K_{4,5}\neq B_{5}$,
$K_{5,5}\neq B_{5}$,

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ uses
$\color[rgb]{0.546875,0.33984375,0.1640625}C_{1,5}=1914$ to generate

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{1,i,5}=\begin{bmatrix}1771&1014&1060&876&1474\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ uses
$\color[rgb]{0.56640625,0.07421875,0.99609375}C_{2,5}=1835$ to generate

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{2,i,5}=\begin{bmatrix}846&249&23&182&1616\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ uses
$\color[rgb]{0.2890625,0.56640625,0.88671875}C_{3,5}=349$ to generate

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{3,i,5}=\begin{bmatrix}1086&2034&1059&351&136\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ uses
$\color[rgb]{0.81640625,0.0078125,0.10546875}C_{4,5}=900$ to generate

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{4,i,5}=\begin{bmatrix}494&1940&219&177&1045\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ uses
$\color[rgb]{0.4921875,0.828125,0.12890625}C_{5,5}=614$ to generate

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{5,i,5}=\begin{bmatrix}1947&931&860&13&94\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ receives

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{i,1,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1771}&{\color[rgb]{0.56640625,0.07421875,0.99609375}846}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1086}&{\color[rgb]{0.81640625,0.0078125,0.10546875}494}&{\color[rgb]{0.4921875,0.828125,0.12890625}1947}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ receives

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{i,2,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1014}&{\color[rgb]{0.56640625,0.07421875,0.99609375}249}&{\color[rgb]{0.2890625,0.56640625,0.88671875}2034}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1940}&{\color[rgb]{0.4921875,0.828125,0.12890625}931}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ receives

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{i,3,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1060}&{\color[rgb]{0.56640625,0.07421875,0.99609375}23}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1059}&{\color[rgb]{0.81640625,0.0078125,0.10546875}219}&{\color[rgb]{0.4921875,0.828125,0.12890625}860}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ receives

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{i,4,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}876}&{\color[rgb]{0.56640625,0.07421875,0.99609375}182}&{\color[rgb]{0.2890625,0.56640625,0.88671875}351}&{\color[rgb]{0.81640625,0.0078125,0.10546875}177}&{\color[rgb]{0.4921875,0.828125,0.12890625}13}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ receives

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{i,5,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1474}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1616}&{\color[rgb]{0.2890625,0.56640625,0.88671875}136}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1045}&{\color[rgb]{0.4921875,0.828125,0.12890625}94}\\\
\end{bmatrix}^{\intercal}}\end{array}.$

According to Algorithm 5, $D_{5}=599$ is generated.

We compute $P_{5}^{n-2}=829$, and then deduct that

$D_{5}\neq P_{5}^{n-2}\implies p_{0,5}=1$

| $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$
---|---|---|---|---|---|---|---|---
$p_{1}=143$ | 1 |  | 0 |  | 0 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{2}=124$ | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{3}=217$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ |  |  $\Lsh$ |  |  $\Lsh$ |
$p_{4}=222$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ |  |  $\Lsh$ |  |  $\Lsh$ |
$p_{5}=86$ | 0 |  | 1 |  | 0 |  |  1 |  | 0 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$\left[~{}p_{0}~{}\right]_{\text{base 2}}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 |  | 1 |  | 0 |  | 1 |  | 1 |  |  |  |  |  |

Table 12: Two or more bidders for $j=5$

For $j=6$, Algorithm 4 generates $B_{6}=346$ and $P_{6}=820$. $K_{1,6}\neq
B_{6}$, $K_{2,6}\neq B_{6}$, $K_{3,6}\neq B_{6}$, $K_{5,6}\neq B_{6}$,
$K_{4,6}=B_{6}$, $\implies$ $\alpha_{4}$ is the only bidder for $j=6$

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}b_{4,4,j}=\begin{bmatrix}977&717&1366&1641&487&1962&1759&1977\\\
\end{bmatrix}}\end{array}$

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ uses
$\color[rgb]{0.546875,0.33984375,0.1640625}C_{1,6}=1206$ to generate

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{1,i,6}=\begin{bmatrix}1149&1790&769&1280&362\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ uses
$\color[rgb]{0.56640625,0.07421875,0.99609375}C_{2,6}=1987$ to generate

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{2,i,6}=\begin{bmatrix}1628&1384&1744&108&531\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ uses
$\color[rgb]{0.2890625,0.56640625,0.88671875}C_{3,6}=454$ to generate

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{3,i,6}=\begin{bmatrix}123&449&1934&702&1110\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ uses
$\color[rgb]{0.81640625,0.0078125,0.10546875}F_{4,6}=946$ to generate

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{4,i,6}=\begin{bmatrix}1289&1265&324&1168&1094\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ uses
$\color[rgb]{0.4921875,0.828125,0.12890625}C_{5,6}=650$ to generate

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{5,i,6}=\begin{bmatrix}604&1621&1261&1846&890\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ receives

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{i,1,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1149}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1628}&{\color[rgb]{0.2890625,0.56640625,0.88671875}123}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1289}&{\color[rgb]{0.4921875,0.828125,0.12890625}604}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ receives

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{i,2,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1790}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1384}&{\color[rgb]{0.2890625,0.56640625,0.88671875}449}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1265}&{\color[rgb]{0.4921875,0.828125,0.12890625}1621}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ receives

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{i,3,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}769}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1744}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1934}&{\color[rgb]{0.81640625,0.0078125,0.10546875}324}&{\color[rgb]{0.4921875,0.828125,0.12890625}1261}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ receives

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{i,4,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1280}&{\color[rgb]{0.56640625,0.07421875,0.99609375}108}&{\color[rgb]{0.2890625,0.56640625,0.88671875}702}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1168}&{\color[rgb]{0.4921875,0.828125,0.12890625}1846}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ receives

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{i,5,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}362}&{\color[rgb]{0.56640625,0.07421875,0.99609375}531}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1110}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1094}&{\color[rgb]{0.4921875,0.828125,0.12890625}890}\\\
\end{bmatrix}^{\intercal}}\end{array}.$

According to Algorithm 5, $D_{6}=305$ is generated.

We compute $P_{6}^{n-2}=305$, and then deduct that

$D_{6}=P_{6}^{n-2}\implies p_{0,6}=0$

| $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$
---|---|---|---|---|---|---|---|---
$p_{1}=143$ | 1 |  | 0 |  | 0 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{2}=124$ | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{3}=217$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ |  |  $\Lsh$ |
$p_{4}=222$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ |  | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ |
$p_{5}=86$ | 0 |  | 1 |  | 0 |  |  1 |  | 0 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$\left[~{}p_{0}~{}\right]_{\text{base 2}}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  |  |  |

Table 13: One or no bidder for $j=6$

For $j=7$, Algorithm 4 generates $B_{7}=915$ and $P_{7}=1070$. $K_{1,7}\neq
B_{7}$, $K_{2,7}\neq B_{7}$, $K_{3,7}\neq B_{7}$, $K_{5,7}\neq B_{7}$,

$K_{4,7}=B_{7}$, $\implies$ $\alpha_{4}$ is the only bidder for $j=7$

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ uses
$\color[rgb]{0.546875,0.33984375,0.1640625}C_{1,7}=1741$ to generate

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{1,i,7}=\begin{bmatrix}1227&110&660&154&1633\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ uses
$\color[rgb]{0.56640625,0.07421875,0.99609375}C_{2,7}=1533$ to generate

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{2,i,7}=\begin{bmatrix}1559&414&1870&1912&1689\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ uses
$\color[rgb]{0.2890625,0.56640625,0.88671875}C_{3,7}=1421$ to generate

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{3,i,7}=\begin{bmatrix}724&1493&88&1058&965\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ uses
$\color[rgb]{0.81640625,0.0078125,0.10546875}F_{4,7}=275$ to generate

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{4,i,7}=\begin{bmatrix}637&374&1388&289&638\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ uses
$\color[rgb]{0.4921875,0.828125,0.12890625}C_{5,7}=1825$ to generate

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{5,i,7}=\begin{bmatrix}1922&1277&1184&1144&306\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ receives

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{i,1,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1227}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1559}&{\color[rgb]{0.2890625,0.56640625,0.88671875}724}&{\color[rgb]{0.81640625,0.0078125,0.10546875}637}&{\color[rgb]{0.4921875,0.828125,0.12890625}1922}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ receives

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{i,2,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}110}&{\color[rgb]{0.56640625,0.07421875,0.99609375}414}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1493}&{\color[rgb]{0.81640625,0.0078125,0.10546875}374}&{\color[rgb]{0.4921875,0.828125,0.12890625}1277}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ receives

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{i,3,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}660}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1870}&{\color[rgb]{0.2890625,0.56640625,0.88671875}88}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1388}&{\color[rgb]{0.4921875,0.828125,0.12890625}1184}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ receives

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{i,4,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}154}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1912}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1058}&{\color[rgb]{0.81640625,0.0078125,0.10546875}289}&{\color[rgb]{0.4921875,0.828125,0.12890625}1144}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ receives

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{i,5,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1633}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1689}&{\color[rgb]{0.2890625,0.56640625,0.88671875}965}&{\color[rgb]{0.81640625,0.0078125,0.10546875}638}&{\color[rgb]{0.4921875,0.828125,0.12890625}306}\\\
\end{bmatrix}^{\intercal}}\end{array}.$

According to Algorithm 5, $D_{7}=592$ is generated.

We compute $P_{7}^{n-2}=592$, and then deduct that

$D_{7}=P_{7}^{n-2}\implies p_{0,7}=0$

| $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$
---|---|---|---|---|---|---|---|---
$p_{1}=143$ | 1 |  | 0 |  | 0 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{2}=124$ | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{3}=217$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ |
$p_{4}=222$ | 1 |  | 1 |  | 0 |  |  1 |  | 1 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ |
$p_{5}=86$ | 0 |  | 1 |  | 0 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$\left[~{}p_{0}~{}\right]_{\text{base 2}}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  |

Table 14: One or no bidder for $j=7$

For $j=8$, Algorithm 4 generates $B_{8}=1843$ and $P_{8}=567$. $K_{1,8}\neq
B_{8}$, $K_{2,8}\neq B_{8}$, $K_{3,8}\neq B_{8}$, $K_{4,8}\neq B_{8}$,
$K_{5,8}\neq B_{8}$,

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ uses
$\color[rgb]{0.546875,0.33984375,0.1640625}C_{1,8}=412$ to generate

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{1,i,8}=\begin{bmatrix}1957&1460&2042&118&1282\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ uses
$\color[rgb]{0.56640625,0.07421875,0.99609375}C_{2,8}=862$ to generate

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{2,i,8}=\begin{bmatrix}181&495&1687&1333&179\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ uses
$\color[rgb]{0.2890625,0.56640625,0.88671875}C_{3,8}=832$ to generate

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{3,i,8}=\begin{bmatrix}1364&78&1282&880&1324\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ uses
$\color[rgb]{0.81640625,0.0078125,0.10546875}C_{4,8}=806$ to generate

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{4,i,8}=\begin{bmatrix}1559&187&250&174&76\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ uses
$\color[rgb]{0.4921875,0.828125,0.12890625}C_{5,8}=1274$ to generate

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{5,i,8}=\begin{bmatrix}900&9&47&469&639\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.546875,0.33984375,0.1640625}\alpha_{1}$ receives

$\begin{array}[]{l}{\color[rgb]{0.546875,0.33984375,0.1640625}d_{i,1,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1957}&{\color[rgb]{0.56640625,0.07421875,0.99609375}181}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1364}&{\color[rgb]{0.81640625,0.0078125,0.10546875}1559}&{\color[rgb]{0.4921875,0.828125,0.12890625}900}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.56640625,0.07421875,0.99609375}\alpha_{2}$ receives

$\begin{array}[]{l}{\color[rgb]{0.56640625,0.07421875,0.99609375}d_{i,2,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1460}&{\color[rgb]{0.56640625,0.07421875,0.99609375}495}&{\color[rgb]{0.2890625,0.56640625,0.88671875}78}&{\color[rgb]{0.81640625,0.0078125,0.10546875}187}&{\color[rgb]{0.4921875,0.828125,0.12890625}9}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.2890625,0.56640625,0.88671875}\alpha_{3}$ receives

$\begin{array}[]{l}{\color[rgb]{0.2890625,0.56640625,0.88671875}d_{i,3,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}2042}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1687}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1282}&{\color[rgb]{0.81640625,0.0078125,0.10546875}250}&{\color[rgb]{0.4921875,0.828125,0.12890625}47}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.81640625,0.0078125,0.10546875}\alpha_{4}$ receives

$\begin{array}[]{l}{\color[rgb]{0.81640625,0.0078125,0.10546875}d_{i,4,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}118}&{\color[rgb]{0.56640625,0.07421875,0.99609375}1333}&{\color[rgb]{0.2890625,0.56640625,0.88671875}880}&{\color[rgb]{0.81640625,0.0078125,0.10546875}174}&{\color[rgb]{0.4921875,0.828125,0.12890625}469}\\\
\end{bmatrix}^{\intercal}}\end{array}$

$\color[rgb]{0.4921875,0.828125,0.12890625}\alpha_{5}$ receives

$\begin{array}[]{l}{\color[rgb]{0.4921875,0.828125,0.12890625}d_{i,5,j}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1282}&{\color[rgb]{0.56640625,0.07421875,0.99609375}179}&{\color[rgb]{0.2890625,0.56640625,0.88671875}1324}&{\color[rgb]{0.81640625,0.0078125,0.10546875}76}&{\color[rgb]{0.4921875,0.828125,0.12890625}639}\\\
\end{bmatrix}^{\intercal}}\end{array}.$

According to Algorithm 5, $D_{8}=725$ is generated.

We compute $P_{8}^{n-2}=1709$, and then deduct that

$D_{8}\neq P_{8}^{n-2}\implies p_{0,8}=1$

| $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$
---|---|---|---|---|---|---|---|---
$p_{1}=143$ | 1 |  | 0 |  | 0 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{2}=124$ | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{3}=217$ | 1 |  | 1 |  | 0 |  |  1 |  | 1 |  | 0 |  | 0 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 1
$p_{4}=222$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ | 1
$p_{5}=86$ | 0 |  | 1 |  | 0 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$\left[~{}p_{0}~{}\right]_{\text{base 2}}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1

Table 15: Two or more bidders for $j=8$

The output price of this Vickrey auction is

$\begin{array}[]{c}p_{0}=(11011001)_{\text{base 2}}=217\\\ \end{array}$

According to the final price verification Algorithm 7, we have

$\begin{array}[]{l}{\mathcal{P}_{l}=\begin{bmatrix}{\color[rgb]{0.546875,0.33984375,0.1640625}1301}&{\color[rgb]{0.56640625,0.07421875,0.99609375}705}&{\color[rgb]{0.2890625,0.56640625,0.88671875}718}&{\color[rgb]{0.81640625,0.0078125,0.10546875}511}&{\color[rgb]{0.4921875,0.828125,0.12890625}150}\\\
\end{bmatrix}^{\intercal}}\end{array}$

Moreover, since there exists $\mathbf{P}_{3}=\mathcal{P}_{3}$, the output
price $p_{0}$ is the original committed second-highest bid. This information
about bidders is also protected by the anonymity of the Internet.

Let $j^{\prime}=7$ be the largest index such that $p_{0,j^{\prime}}=0$. The
winner $\alpha_{4}$ sends the seller $K_{u,4,7}$ for $\forall u$ which can be
verified by checking if

$\prod_{u=1}^{n}K_{u,4,7}=B_{7}$ (62)

| $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$
---|---|---|---|---|---|---|---|---
$p_{1}=143$ | 1 |  | 0 |  | 0 |  | 0 |  | 1 |  | 1 |  | 1 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{2}=124$ | 0 |  | 1 |  | 1 |  | 1 |  | 1 |  | 1 |  | 0 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$p_{3}=217$ | 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 1
$p_{4}=222$ | 1 |  |  1 |  | 0 |  | 1 |  | 1 |  | 1 |  |  1 |  | 0 |
$\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 |  $\Lsh$ | 1 |  $\Lsh$ | 1 |  $\Lsh$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ | 0 | $\rotatebox[origin={c}]{180.0}{$\Lsh$}_{\color[rgb]{0.81640625,0.0078125,0.10546875}1}$ | 1
$p_{5}=86$ | 0 |  | 1 |  | 0 |  | 1 |  | 0 |  | 1 |  |  1 |  | 0 |
$\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0 |  $\Lsh$ | 0
$\left[~{}p_{0}~{}\right]_{\text{base 2}}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 |  | 1 |  | 0 |  | 1 |  | 1 |  | 0 |  | 0 |  | 1

Table 16:  In the yellow cell at the bottom, it can be observed that the
winner $\alpha_{4}$ is the only bidder who placed a ‘1’ at digit
$j^{\prime}=7$. Therefore, $\alpha_{4}$ is willing to pay a price that is at
least one bid higher than the second-highest bid, which is represented by
$p_{4}~{}\geq~{}p_{0}+1=(11011010)_{\text{base 2}}$