# Fast Triangle Counting

David A. Bader∗ Department of Data Science
New Jersey Institute of Technology
Newark, New Jersey, USA
<EMAIL_ADDRESS>
###### Abstract

Listing and counting triangles in graphs is a key algorithmic kernel for
network analyses including community detection, clustering coefficients,
k-trusses, and triangle centrality. We design and implement a new serial
algorithm for triangle counting that performs competitively with the fastest
previous approaches on both real and synthetic graphs, such as those from the
Graph500 Benchmark and the MIT/Amazon/IEEE Graph Challenge. The experimental
results use the recently-launched Intel Xeon Platinum 8480+ and CPU Max 9480
processors.

###### Index Terms:

Graph Algorithms, Triangle Counting, High Performance Data Analytics

${}^{*}$${}^{*}$footnotetext: This research was partially supported by NSF
grant number CCF-2109988.

##  I Introduction

Triangle listing and counting is a highly-studied problem in computer science
and is a key building block in various graph analysis techniques such as
clustering coefficients [1], k-truss [2], and triangle centrality [3]. The
MIT/Amazon/IEEE Graph Challenge [4, 5] includes triangle counting as a
fundamental method in graph analytics. There are at most ${n\choose
3}=\mbox{\mbox{$\Theta$}$\left(n^{3}\right)$}$ triangles in a graph $G=(V,E)$
with $n=|V|$ vertices and $m=|E|$ edges. The focus of this paper is on
sequential triangle counting algorithms for sparse graphs that are stored in
compressed, sparse row (CSR) format, rather than adjacency matrix format. The
naïve approach using triply-nest loops to check if each triple $(u,v,w)$ forms
a triangle takes $\mathcal{O}\left(n^{3}\right)$ time and is inefficient for
sparse graphs. It is well-known that listing all triangles in G is
$\Omega$$\left(m^{\frac{3}{2}}\right)$ time [6, 7].

The main contributions of this paper are:

  * •

A new triangle algorithm that combines the techniques of cover-edges, forward,
and hashing and runs in $\mathcal{O}\left(m\cdot a(G)\right)$, where $a(G)$ is
the arboricity of the graph;

  * •

An experimental study of an implementation of this novel triangle counting
algorithm on real and synthetic graphs; and

  * •

Freely-available, open-source software for more than 20 triangle counting
algorithms and variants in the C programming language.

###  I-A Related work

There are faster algorithms for triangle counting, such as the work of Alon,
Yuster, and Zwick [8] that require an adjacency matrix for the input graph
representation and use fast matrix multiplication. As this is infeasible for
large, sparse graph, their and other fast multiply methods are outside the
scope of this paper.

Latapy [7] provides a survey on triangle counting algorithms for very large,
sparse graphs. One of the earliest algorithms, _tree-listing_ , published in
1978 by Itai and Rodeh [6] first finds a rooted spanning tree of the graph.
After iterating through the non-tree edges and using criteria to identify
triangles, the tree edges are removed and the algorithm repeats until there
are no edges remaining. This approach takes
$\mathcal{O}\left(m^{\frac{3}{2}}\right)$ time (or $\mathcal{O}\left(n\right)$
for planar graphs).

The most common triangle counting algorithms in the literature include
_vertex-iterator_ [6, 7] and _edge-iterator_ [6, 7] approaches that run in
$\mathcal{O}\left(m\cdot d_{\mbox{max}}\right)$ time [6, 9, 10], where
$d_{\mbox{max}}$ is the maximum degree of a vertex in the graph. In vertex-
iterator, the adjacency list $N(v)$ of each vertex $v\in V$ is doubly-
enumerated to find all 2-paths $(u,v,w)$ where $u,w\in N(v)$. Then, the graph
is searched for the existence of the closing edge $(u,w)$ by checking if $w\in
N(u)$ (or if $u\in N(w)$). Arifuzzaman  _et al._ [11] study modifications of
the vertex-iterator algorithm based on various methods for vertex ordering.

In edge-iterator, each edge $(u,v)$ in the graph is examined, and the
intersection of $N(u)$ and $N(v)$ is computed to find triangles. A common
optimization is to use a _direction-oriented_ approach that only considers
edges $(u,v)$ where $u<v$. The variants of edge-iterator are often based on
the algorithm used to perform the intersection. When the two adjacency lists
are sorted, then _MergePath_ and _BinarySearch_ can be used. MergePath
performs a linear scan through both lists counting the common elements.
Makkar, Bader and Green [12] give an efficient MergePath algorithm for GPU.
Mailthody  _et al._ [13] use an optimized two-pointer intersection (MergePath)
for set intersection. BinarySearch, as the name implies, uses a binary search
to determine if each element of the smaller list is found in the larger list.
_Hash_ is another method for performing the intersection of two sets and it
does not require the adjacency lists to be sorted. A typical implementation of
Hash initializes a Boolean array of size $m$ to all false. Then, positions in
Hash corresponding to the vertex values in $N(u)$ are set to true. Then $N(v)$
is scanned, looking up in $\Theta$$\left(1\right)$ time whether or not there
is a match for each vertex. Chiba and Nishizeki published one of the earliest
edge iterator with hashing algorithms for triangle finding in 1985 [14]. The
running time is $\mathcal{O}\left(a(G)m\right)$, where $a(G)$ is defined as
the arboricity of $G$, which is upper-bounded
$a(G)\leq\lceil(2m+n)^{\frac{1}{2}}/2\rceil$ [14]. In 2018, Davis rediscovered
this method, which he calls tri_simple in his comparison with SuiteSparse
GraphBLAS [15]. According to Davis [15]: this algorithm “is already a non-
trivial method. It requires expert knowledge of how Gustavson’s method can be
implemented efficiently, including a reduction of the result to a single
scalar.” Mowlaei [16] gave a variant of the edge-iterator algorithm that uses
vectorized sorted set intersection and reorders the vertices using the reverse
Cuthill-McKee heuristic.

In 2005, Schank and Wagner [9, 10] designed a fast triangle counting algorithm
called _forward_ (see Algorithm 1) that is a refinement of the edge-iterator
approach. Instead of intersections of the full adjacency lists, the _forward_
algorithm uses a dynamic data structure $A(v)$ to store a subset of the
neighborhood $N(v)$ for $v\in V$. Initially each set $A()$ is empty, and after
computing the intersection of the sets $A(u)$ and $A(v)$ for each edge $(u,v)$
(with $u<v$), $u$ is added to $A(v)$. This significantly reduces the size of
the intersections needed to find triangles. The running time is
$\mathcal{O}\left(m\cdot d_{\mbox{max}}\right)$. However, if one reorders the
vertices in decreasing order of their degrees as a $\Theta$$\left(n\log
n\right)$ time pre-processing step, the forward algorithm’s running time
reduces to $\mathcal{O}\left(m^{\frac{3}{2}}\right)$. Donato  _et al._ [17]
implement the forward algorithm for shared-memory. Ortmann and Brandes [18]
survey triangle counting algorithms, create a unifying framework for
parsimonious implementations, and conclude that nearly every triangle listing
variant is in $\mathcal{O}\left(m\cdot a(G)\right)$.

Algorithm 1 Forward Triangle Counting [9, 10]

1:Graph $G=(V,E)$

2:Triangle Count $T$

3:$T\leftarrow 0$

4:$\forall v\in V$

5: $A(v)\leftarrow\emptyset$

6:$\forall(u,v)\in E$

7: if $(u<v)$ then

8: $\forall w\in A(u)\cap A(v)$

9: $T\leftarrow T+1$

10: $A(v)\leftarrow A(v)\cup\\{u\\}$

The _forward-hashed_ algorithm [9, 10] (also called _compact-forward_ [7]) is
a variant of the forward algorithm that uses the hashing described above for
the intersections of the $A()$ sets, see Algorithm 2. Shun and Tangwongsan
[19] parallelize the forward and forward-hashed algorithms for multicore
systems. Low  _et al._ [20] derive a linear-algebra method for triangle
counting that does not use matrix multiplication. Their algorithm results in
the forward-hashed algorithm.

Algorithm 2 Forward-Hashed Triangle Counting [9, 10]

1:Graph $G=(V,E)$

2:Triangle Count $T$

3:$T\leftarrow 0$

4:$\forall v\in V$

5: $A(v)\leftarrow\emptyset$

6:$\forall(u,v)\in E$

7: if $(u<v)$ then

8: $\forall w\in A(u)$

9: Hash[$w$] $\leftarrow$ true

10: $\forall w\in A(v)$

11: if Hash[$w$] then

12: $T\leftarrow T+1$

13: $\forall w\in A(u)$

14: Hash[$w$] $\leftarrow$ false

15: $A(v)\leftarrow A(v)\cup\\{u\\}$

##  II Algorithm

Recently, we presented Algorithm 3 [21] as a new method for finding triangles.
This approach finds a subset of _cover edges_ from $E$ such that every
triangle contains at least one cover edge.

Algorithm 3 Cover-Edge Triangle Counting [21]

1:Graph $G=(V,E)$

2:Triangle Count $T$

3:$T\leftarrow 0$

4:$\forall v\in V$

5: if $v$ unvisited, then BFS($G$, $v$)

6:$\forall(u,v)\in E$

7: if $(L(u)\equiv L(v))\land(u<v)$ $\triangleright$ $(u,v)$ is horizontal

8: $\forall w\in N(u)\cap N(v)$

9: if $(L(u)\neq L(w))\lor\left((L(u)\equiv L(w))\land(v<w)\right)$ then

10: $T\leftarrow T+1$

This algorithm uses breadth-first search (BFS) to find a reduced cover-edge
set consisting of edges $(u,v)$ where the levels of vertices $u$ and $v$ are
the same, i.e., $L(u)\equiv L(v)$. From the result in [21], each triangle must
contain at least one of these horizontal edges. Then each edge in the cover
set is examined, and Hash is used to find the vertices $w$ in the intersection
of $N(u)$ and $N(v)$. A triangle $(u,v,w)$ is found based on logic about $w$’s
level. The breadth-first search, including determining the level of each
vertex and marking horizontal-edges, requires $\mathcal{O}\left(n+m\right)$
time. The number of horizontal edges is $\mathcal{O}\left(m\right)$. The
intersection of each pair of vertices costs
$\mathcal{O}\left(d_{\mbox{max}}\right)$. Hence, Alg. 3 has complexity
$\mathcal{O}\left(m\cdot d_{\text{max}}\right)$.

Algorithm 4 Fast Triangle Counting

1:Graph $G=(V,E)$

2:Triangle Count $T$

3:$\forall v\in V$

4: if $v$ unvisited, then BFS($G$, $v$)

5:$\forall(u,v)\in E$

6: if $(L(u)\equiv L(v))$ then $\triangleright$ $(u,v)$ is horizontal

7: Add $(u,v)$ to $G0$

8: else

9: Add $(u,v)$ to $G1$

10:$T\leftarrow\mbox{TC}\\_{\mbox{forward-hashed}}(G0)$ $\triangleright$ Alg.
2

11:$\forall u\in V_{G1}$

12: $\forall v\in N_{G1}(u)$

13: Hash[$v$] $\leftarrow$ true

14: $\forall v\in N_{G0}(u)$

15: if $(u<v)$ then

16: $\forall w\in N_{G1}(v)$

17: if Hash[$w$] then

18: $T\leftarrow T+1$

19: $\forall v\in N_{G1}(u)$

20: Hash[$v$] $\leftarrow$ false

In this paper, we present our new triangle counting algorithm (Alg. 4), called
_fast triangle counting_. This new triangle counting algorithm is similar with
cover-edge triangle counting in Alg. 3 and uses BFS to assign a level to each
vertex in lines 3 and 4. Next in lines 5 to 9, the edges $E$ of the graph are
partitioned into two sets $E0$ – the horizontal edges where both endpoints are
on the same level – and $E1$ – the remaining tree and non-tree edges that span
a level. Thus, we now have two graphs, $G0=(V,E0)$ and $G1=(V,E1)$, where
$E=E0\cup E1$ and $E0\cap E1=\emptyset$. Triangles that are fully in $G0$ are
counted with one method and triangles not fully in $G0$ are counted with
another method. For $G0$, the graph with horizontal edges, we count the
triangles efficiently using the forward-hashed method (line 10). For triangles
not fully in $G0$, the algorithm uses the following approach to count these
triangles. Using $G1$, the graph that contains the edges that span levels, we
use a hashed intersection approach in lines 11 to 20. As per the cover-edge
triangle counting, we need to find the intersections of the adjacency lists
from the endpoints of horizontal edges. Thus, we use $G0$ to select the edges,
and perform the hash-based intersections from the adjacency lists in graph
$G1$. The proof of correctness for cover-edge triangle counting is given in
[21]. Alg. 4 is a hybrid version of this algorithm, that partitions the edge
set, and uses two different methods to count these two types of triangles. The
proof of correctness is still valid with these new refinements to the
algorithm. The running time of Alg. 4 is the maximum of the running time of
forward-hashing and Alg. 3. Alg. 4 uses hashing for the set intersections. For
vertices $u$ and $v$ the cost is $\min(d(u),d(v))$ since the algorithm can
check if the neighbors of the lower-degree endpoint are in the hash set of the
higher-degree endpoint. Over all $(u,v)$ edges in $E$, these intersections
take $\mathcal{O}\left(m\cdot a(G)\right)$ expected time. Hence, Alg. 4 takes
$\mathcal{O}\left(m\cdot a(G)\right)$ expected time.

Similar with the forward-hashed method, by pre-processing the graph by re-
ordering the vertices in decreasing order of degree in $\Theta$$\left(n\log
n\right)$ time often leads to a faster triangle counting algorithm in
practice.

##  III Experimental Results

We implemented more than 20 triangle counting algorithms and variants in C and
use the Intel Development Cloud for benchmarking our results on a GNU/Linux
node. The compiler is Intel(R) oneAPI DPC++/C++ Compiler 2023.1.0
(2023.1.0.20230320) and ‘-O2‘ is used as a compiler optimization flag. For
benchmarking we compare the performance using two recently-launched Intel Xeon
processors (Sapphire Rapids launched Q1’23) with two types of memory (DDR5 and
HBM). The first node is a dedicated 2.00 GHz 56-core (112 thread) Intel(R)
Xeon(R) Platinum 8480+ processor (formerly known as Sapphire Rapids) with 105M
cache and 1024GB of DDR5 RAM. The second node is a dedicated 1.90 GHz 56-core
(112 thread) Intel(R) Xeon(R) CPU Max 9480 processor (formerly known as
Sapphire Rapids HBM) with 112.5M cache and 256GB of high-memory bandwidth
(HBM) memory.

Following the best practices of experimental algorithmics [22], we conduct the
benchmarking as follows. Each algorithm is written in C and has a single
argument – a pointer to the graph in a compressed sparse row (CSR) format. The
input is treated as read-only. If the implementation needs auxiliary arrays,
pre-processing steps, or additional data structures, it is charged the full
cost. Each implementation must manage memory and not contain any memory leaks
– hence, any dynamically allocated memory must be freed prior to returning the
result. The output from each implementation is an integer with the number of
triangles found. Each algorithm is run ten times, and the mean running time is
reported. To reduce variance for random graphs, the same graph instance is
used for all of the experiments. The source code is sequential C code without
any explicit parallelization. The same coding style and effort was used for
each implementation.

Experimental results are presented in Table I for the Intel Xeon Platinum
8480+ processor with DDR5 memory and in Table II for the Intel Xeon Max 9480
processor with HBM memory. For each graph, we give the number of vertices
($n$), the number of edges ($m$), the number of triangles, and $k$ – the
percentage of graph edges that are horizontal after running BFS from arbitrary
roots. The algorithms tested are

IR

: Treelist from Itai-Rodeh [6]

V

: Vertex-iterator

VD

: Vertex Iterator (direction-oriented)

EM

: Edge Iterator with MergePath for set intersection

EMD

: Edge Iterator with MergePath for set intersection (direction-oriented)

EB

: Edge Iterator with BinarySearch for set intersection

EBD

: Edge Iterator with BinarySearch for set intersection (direction-oriented)

EP

: Edge Iterator with Partitioning for set intersection

EPD

: Edge Iterator with Partitioning for set intersection (direction-oriented)

EH

: Edge Iterator with Hashing for set intersection

EHD

: Edge Iterator with Hashing for set intersection (direction-oriented)

F

: Forward

FH

: Forward with Hashing

FHD

: Forward with Hashing and degree-ordering

TS

: Tri_simple (Davis [15])

LA

: Linear Algebra (CMU [20])

CE

: Cover Edge (Bader, [21])

CED

: Cover Edge with degree-ordering (Bader, [21])

Bader

: this paper

BaderD

: this paper with degree-ordering

While all of the algorithms tested have the same asymptotic worst-case
complexity, the running times range by orders of magnitude between the
approaches. In nearly every case where edge direction-orientation is used, the
performance is typically improved by a constant factor up to two. The vertex-
iterator and Itah-Rodeh algorithms are the slowest across the real and
synthetic datasets. The timings between the Intel Xeon Platinum 8480+ and
Intel Xeon Max 9480 are consistent, with the 8480+ a few percent faster than
the 9480 processor. This is likely due to the fact that we are using single-
threaded code on one core, and that the 8480+ is clocked at a slightly higher
rate (2.00GHz vs 1.90GHz).

In general, the forward algorithms and its variants tend to perform the
fastest, followed by the edge-iterator, and then the vertex-iterator methods.
The new fast triangle counting algorithm is competitive with the forward
approaches, and may be useful when the results of a BFS are already available
from the analyst’s workflow, which is often the case.

The performance of the road network graphs (roadNet-CA, roadNet-PA, roadNet-
TX) are outliers from the other graphs. Road networks, unlike social networks,
often have only low degree vertices (for instance, many degree four vertices),
and large diameters. The percentage of horizontal edges ($k$) of these road
networks is under 15% and we see less benefit of the new approach due to this
low value of $k$. In addition, the sorting of vertices by degree for the road
network significantly harms the performance compared with the default ordering
of the input. This may be due to the fact that there are few unique degree
values, and sorting decimates the locality in the graph data structure.

The linear algebra approach [20] does not typically perform as well on the
real and synthetic social networks. For example, on a large RMAT graph of
scale 18, the linear algebra algorithm method takes seconds, whereas the new
algorithm runs in under a second. However, the linear algebra approach
performs well on the road networks.

##  IV Conclusions

In this paper we design and implement a novel, fast triangle counting
algorithm, that uses new techniques to improve the performance. It is the
first algorithm in decades to shine new light on triangle counting, and use a
wholly new method of cover-edges to reduce the work of set intersections,
rather than other approaches that are variants of the well-known vertex-
iterator and edge-iterator methods. We provide extensive performance results
in a parsimonious framework for benchmarking serial triangle counting
algorithms for sparse graphs in a uniform manner. The results use one of
Intel’s latest processor families, the Intel Sapphire Rapids (Platinum 8480+)
and Sapphire Rapids HBM (CPU Max 9480) launched in the 1st quarter of 2023.
The new triangle counting algorithm can benefit when the results of a BFS are
available, which is often the case in network science. Additionally, this work
will inspire much interest within the Graph Challenge community to implement
versions of the presented algorithms for large-shared memory, distributed
memory, GPU, or multi-GPU frameworks.

##  V Future Work

The fast triangle counting algorithm (Alg. 4) can be readily parallelized
using a parallel BFS, partitioning the edge set in parallel, and using a
parallel triangle counting algorithm on graph $G0$, and parallelizing the set
intersections for graph $G1$. In future work, we will implement this parallel
algorithm and compare its performance with other parallel approaches.

##  VI Reproducibility

The sequential triangle counting source code is open source and available on
GitHub at https://github.com/Bader-Research/triangle-counting. The input
graphs are from the Stanford Network Analysis Project (SNAP) available from
http://snap.stanford.edu/.

## References

  * [1] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [2] J. Cohen, “Trusses: Cohesive subgraphs for social network analysis,” _National Security Agency Technical Report_ , vol. 16, no. 3.1, 2008.
  * [3] P. Burkhardt, “Triangle centrality,” _CoRR_ , vol. abs/2105.00110, 2021. [Online]. Available: https://arxiv.org/abs/2105.00110
  * [4] S. Samsi, V. Gadepally, M. Hurley, M. Jones, E. Kao, S. Mohindra, P. Monticciolo, A. Reuther, S. Smith, W. Song, D. Staheli, and J. Kepner, “GraphChallenge.org: Raising the bar on graph analytic performance,” in _2018 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2018, pp. 1–7.
  * [5] S. Samsi, J. Kepner, V. Gadepally, M. Hurley, M. Jones, E. Kao, S. Mohindra, A. Reuther, S. Smith, W. Song, D. Staheli, and P. Monticciolo, “Graphchallenge.org triangle counting performance,” in _2020 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2020, pp. 1–9.
  * [6] A. Itai and M. Rodeh, “Finding a minimum circuit in a graph,” _SIAM Journal on Computing_ , vol. 7, no. 4, pp. 413–423, 1978.
  * [7] M. Latapy, “Main-memory triangle computations for very large (sparse (power-law)) graphs,” _Theoretical Computer Science_ , vol. 407, no. 1, pp. 458–473, 2008.
  * [8] N. Alon, R. Yuster, and U. Zwick, “Finding and counting given length cycles,” _Algorithmica_ , vol. 17, no. 3, pp. 209–223, 1997.
  * [9] T. Schank and D. Wagner, “Finding, counting and listing all triangles in large graphs, an experimental study,” in _Proceedings of the 4th International Conference on Experimental and Efficient Algorithms_ , ser. WEA’05. Berlin, Heidelberg: Springer-Verlag, 2005, p. 606–609.
  * [10] T. Schank, “Algorithmic aspects of triangle-based network analysis,” Ph.D. dissertation, Karlsruhe Institute of Technology, 2007.
  * [11] S. Arifuzzaman, M. Khan, and M. Marathe, “Fast parallel algorithms for counting and listing triangles in big graphs,” _ACM Trans. Knowl. Discov. Data_ , vol. 14, no. 1, Dec 2019.
  * [12] D. Makkar, D. A. Bader, and O. Green, “Exact and parallel triangle counting in dynamic graphs,” in _24th IEEE International Conference on High Performance Computing, HiPC 2017, Jaipur, India, December 18-21, 2017_. Los Alamitos, CA: IEEE Computer Society, 2017, pp. 2–12.
  * [13] V. S. Mailthody, K. Date, Z. Qureshi, C. Pearson, R. Nagi, J. Xiong, and W.-m. Hwu, “Collaborative (cpu + gpu) algorithms for triangle counting and truss decomposition,” in _2018 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2018, pp. 1–7.
  * [14] N. Chiba and T. Nishizeki, “Arboricity and subgraph listing algorithms,” _SIAM Journal on Computing_ , vol. 14, no. 1, pp. 210–223, 1985.
  * [15] T. A. Davis, “Graph algorithms via suitesparse: Graphblas: triangle counting and k-truss,” in _2018 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2018, pp. 1–6.
  * [16] S. Mowlaei, “Triangle counting via vectorized set intersection,” in _2017 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2017, pp. 1–5.
  * [17] E. Donato, M. Ouyang, and C. Peguero-Isalguez, “Triangle counting with a multi-core computer,” in _2018 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2018, pp. 1–7.
  * [18] M. Ortmann and U. Brandes, “Triangle listing algorithms: Back from the diversion,” in _Proceedings of the Meeting on Algorithm Engineering & Expermiments_. USA: Society for Industrial and Applied Mathematics, 2014, p. 1–8.
  * [19] J. Shun and K. Tangwongsan, “Multicore triangle computations without tuning,” in _2015 IEEE 31st International Conference on Data Engineering_. IEEE, 2015, pp. 149–160.
  * [20] T. M. Low, V. N. Rao, M. Lee, D. Popovici, F. Franchetti, and S. McMillan, “First look: Linear algebra-based triangle counting without matrix multiplication,” in _2017 IEEE High Performance Extreme Computing Conference (HPEC)_ , 2017, pp. 1–6.
  * [21] D. A. Bader, F. Li, A. Ganeshan, A. Gundogdu, J. Lew, O. A. Rodriguez, and Z. Du, “Triangle counting through cover-edges,” in _The 27th Annual IEEE High Performance Extreme Computing Conference (HPEC), Virtual, September 25-29, 2023_ , 2023.
  * [22] C. C. McGeoch, _A Guide to Experimental Algorithmics_ , 1st ed. USA: Cambridge University Press, 2012.

TABLE I: Execution time (in seconds) for Intel Xeon 8480.
Key: IR: Itai-Rodeh. V: Vertex-iterator. VD: Vertex Iterator (direction-oriented). EM: Edge Iterator with MergePath. EMD: Edge Iterator with MergePath (direction-oriented). EB: Edge Iterator with BinarySearch. EBD: Edge Iterator with BinarySearch (direction-oriented). EP: Edge Iterator with Partitioning. EPD: Edge Iterator with Partitioning (direction-oriented). EH: Edge Iterator with Hashing. EHD: Edge Iterator with Hashing (direction-oriented). F: Forward. FH: Forward with Hashing. FHD: Forward with Hashing (degree-order). TS: Tri_simple (Davis) LA: Linear Algebra (CMU). CE: Cover Edge. CED: Cover Edge (degree-order). Bader: this paper. BaderD: this paper with degree-order. Graph | n | m | # triangles | IR | V | VD | EM | EMD | EB | EBD |  |  $k$ (%) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---
karate | 34 | 78 | 45 | 0.000080 | 0.000019 | 0.000007 | 0.000012 | 0.000006 | 0.000018 | 0.000009 |  | 35.9 |
RMAT 6 | 64 | 1024 | 9100 | 0.000599 | 0.001716 | 0.000329 | 0.000404 | 0.000201 | 0.000828 | 0.000392 |  | 93.8 |
RMAT 7 | 128 | 2048 | 18855 | 0.003449 | 0.005494 | 0.001569 | 0.002001 | 0.001014 | 0.004508 | 0.002206 |  | 90.9 |
RMAT 8 | 256 | 4096 | 39602 | 0.005339 | 0.009073 | 0.002575 | 0.002865 | 0.001447 | 0.006661 | 0.003290 |  | 87.6 |
RMAT 9 | 512 | 8192 | 86470 | 0.017020 | 0.054048 | 0.014320 | 0.014765 | 0.007357 | 0.030639 | 0.015200 |  | 87.2 |
RMAT 10 | 1024 | 16384 | 187855 | 0.054833 | 0.093701 | 0.023941 | 0.020353 | 0.010080 | 0.045417 | 0.022546 |  | 82.8 |
RMAT 11 | 2048 | 32768 | 408876 | 0.168952 | 0.314510 | 0.077261 | 0.053464 | 0.026608 | 0.107207 | 0.053023 |  | 81.1 |
RMAT 12 | 4096 | 65536 | 896224 | 0.521454 | 1.083800 | 0.266666 | 0.140524 | 0.069853 | 0.287587 | 0.142856 |  | 77.5 |
RMAT 13 | 8192 | 131072 | 1988410 | 1.703786 | 3.735357 | 0.881334 | 0.372492 | 0.185039 | 0.725695 | 0.360435 |  | 74.9 |
RMAT 14 | 16384 | 262144 | 4355418 | 5.503025 | 13.078101 | 3.134624 | 0.982963 | 0.488870 | 1.792365 | 0.889259 |  | 70.5 |
RMAT 15 | 32768 | 524288 | 9576800 | 18.387938 | 45.361382 | 10.564304 | 2.615737 | 1.299128 | 4.741772 | 2.339147 |  | 68.4 |
RMAT 16 | 65536 | 1048576 | 21133772 | 60.224978 | 157.221897 | 35.818787 | 6.911778 | 3.434474 | 11.763857 | 5.776435 |  | 65.5 |
RMAT 17 | 131072 | 2097152 | 46439638 | 200.686691 | 549.218245 | 124.670216 | 18.305755 | 9.104815 | 30.948553 | 15.177363 |  | 62.8 |
RMAT 18 | 262144 | 4194304 | 101930789 | 665.063581 | 1890.988599 | 421.402839 | 48.163023 | 23.976539 | 78.511757 | 38.472993 |  | 60.3 |
amazon0302 | 262111 | 899792 | 717719 | 0.328209 | 0.239097 | 0.054081 | 0.137364 | 0.064924 | 0.190950 | 0.090092 |  | 44.2 |
amazon0312 | 400727 | 2349869 | 3686467 | 2.101546 | 1.331771 | 0.405438 | 0.714218 | 0.348752 | 1.003573 | 0.471135 |  | 52.4 |
amazon0505 | 410236 | 2439437 | 3951063 | 1.921873 | 1.541379 | 0.443954 | 0.753439 | 0.367458 | 1.069800 | 0.502501 |  | 52.7 |
amazon0601 | 403394 | 2443408 | 3986507 | 1.837775 | 1.445394 | 0.445080 | 0.750829 | 0.366805 | 1.072656 | 0.504409 |  | 52.8 |
loc-Brightkite | 58228 | 214078 | 494728 | 0.538046 | 0.482041 | 0.135135 | 0.115865 | 0.057923 | 0.176090 | 0.087252 |  | 43.2 |
loc-Gowalla | 196591 | 950327 | 2273138 | 5.330385 | 11.300779 | 3.612550 | 2.082631 | 1.035008 | 1.227245 | 0.593189 |  | 50.8 |
roadNet-CA | 1971281 | 2766607 | 120676 | 0.588213 | 0.070164 | 0.032603 | 0.095966 | 0.061715 | 0.102809 | 0.067910 |  | 14.5 |
roadNet-PA | 1090920 | 1541898 | 67150 | 0.329371 | 0.078338 | 0.036759 | 0.103484 | 0.066274 | 0.098181 | 0.038547 |  | 14.6 |
roadNet-TX | 1393383 | 1921660 | 82869 | 0.454882 | 0.088063 | 0.022855 | 0.066163 | 0.042529 | 0.070018 | 0.046474 |  | 14.0 |
soc-Epinions1 | 75888 | 405740 | 1624481 | 4.561436 | 6.073439 | 1.503663 | 0.614835 | 0.304728 | 1.120885 | 0.552059 |  | 53.3 |
wiki-Vote | 8297 | 100762 | 608389 | 0.496671 | 1.027744 | 0.175467 | 0.123803 | 0.061619 | 0.284746 | 0.141419 |  | 54.3 |
Graph | EP | EPD | EH | EHD | F | FH | FHD | TS | LA | CE | CED | Bader | BaderD
karate | 0.000033 | 0.000015 | 0.000009 | 0.000005 | 0.000004 | 0.000004 | 0.000007 | 0.000005 | 0.000002 | 0.000006 | 0.000009 | 0.000009 | 0.000010
RMAT 6 | 0.000928 | 0.000494 | 0.000064 | 0.000031 | 0.000033 | 0.000014 | 0.000016 | 0.000023 | 0.000023 | 0.000049 | 0.000042 | 0.000022 | 0.000021
RMAT 7 | 0.005205 | 0.002781 | 0.000375 | 0.000170 | 0.000216 | 0.000068 | 0.000073 | 0.000120 | 0.000197 | 0.000456 | 0.000336 | 0.000125 | 0.000110
RMAT 8 | 0.007306 | 0.003950 | 0.000467 | 0.000230 | 0.000334 | 0.000114 | 0.000113 | 0.000181 | 0.000309 | 0.000640 | 0.000510 | 0.000164 | 0.000177
RMAT 9 | 0.036358 | 0.019781 | 0.002201 | 0.001108 | 0.001710 | 0.000548 | 0.000562 | 0.000910 | 0.001568 | 0.001564 | 0.001335 | 0.000409 | 0.000413
RMAT 10 | 0.049769 | 0.027202 | 0.002840 | 0.001429 | 0.002386 | 0.000656 | 0.000668 | 0.001255 | 0.002187 | 0.003785 | 0.003294 | 0.000948 | 0.000937
RMAT 11 | 0.129236 | 0.071272 | 0.007045 | 0.003576 | 0.006154 | 0.001528 | 0.001460 | 0.003294 | 0.005603 | 0.008990 | 0.007992 | 0.002005 | 0.002110
RMAT 12 | 0.332512 | 0.184829 | 0.017642 | 0.008948 | 0.015684 | 0.003520 | 0.003302 | 0.008275 | 0.014181 | 0.021089 | 0.018934 | 0.004383 | 0.004499
RMAT 13 | 0.852811 | 0.477536 | 0.044770 | 0.022457 | 0.040657 | 0.008140 | 0.007430 | 0.021401 | 0.035921 | 0.049489 | 0.044248 | 0.009687 | 0.009740
RMAT 14 | 2.197651 | 1.241093 | 0.115374 | 0.056890 | 0.104338 | 0.018856 | 0.016352 | 0.056593 | 0.090133 | 0.113669 | 0.101336 | 0.020978 | 0.020060
RMAT 15 | 5.611216 | 3.182339 | 0.316977 | 0.153824 | 0.271538 | 0.046304 | 0.038232 | 0.161525 | 0.228835 | 0.268428 | 0.236885 | 0.048083 | 0.043707
RMAT 16 | 14.381678 | 8.204573 | 1.055079 | 0.514223 | 0.710508 | 0.119594 | 0.096148 | 0.502529 | 0.583421 | 0.634558 | 0.548067 | 0.118334 | 0.098932
RMAT 17 | 37.158095 | 21.256965 | 3.256451 | 1.640081 | 1.864839 | 0.334746 | 0.251170 | 1.451738 | 1.484360 | 1.497880 | 1.261575 | 0.330477 | 0.249333
RMAT 18 | 93.966516 | 54.116325 | 9.170543 | 4.523967 | 4.845280 | 0.909296 | 0.611022 | 3.957162 | 3.743856 | 3.509278 | 2.888053 | 0.907862 | 0.624522
amazon0302 | 0.314972 | 0.209145 | 0.064610 | 0.032767 | 0.024226 | 0.020652 | 0.041335 | 0.037947 | 0.022963 | 0.044121 | 0.066253 | 0.043772 | 0.060910
amazon0312 | 1.577489 | 0.888635 | 0.289698 | 0.137439 | 0.107685 | 0.075531 | 0.139509 | 0.164931 | 0.100935 | 0.147793 | 0.198154 | 0.129337 | 0.188718
amazon0505 | 1.680979 | 0.942646 | 0.302644 | 0.143367 | 0.113673 | 0.078874 | 0.146358 | 0.172100 | 0.106964 | 0.154702 | 0.208559 | 0.130193 | 0.178938
amazon0601 | 1.675168 | 0.941213 | 0.300678 | 0.142704 | 0.114721 | 0.080125 | 0.145550 | 0.170971 | 0.107216 | 0.155132 | 0.208443 | 0.130382 | 0.178437
loc-Brightkite | 0.262203 | 0.152707 | 0.026410 | 0.013830 | 0.011533 | 0.006663 | 0.010069 | 0.013557 | 0.011688 | 0.011810 | 0.015568 | 0.008635 | 0.013218
loc-Gowalla | 2.840775 | 2.060617 | 0.358680 | 0.175656 | 0.085123 | 0.039745 | 0.056709 | 0.188951 | 0.079884 | 0.074447 | 0.091355 | 0.046396 | 0.064264
roadNet-CA | 0.167447 | 0.093240 | 0.067984 | 0.049379 | 0.032793 | 0.038295 | 0.172404 | 0.051017 | 0.039746 | 0.081306 | 0.209616 | 0.132360 | 0.242484
roadNet-PA | 0.095960 | 0.053119 | 0.038335 | 0.027772 | 0.018091 | 0.021191 | 0.084368 | 0.028920 | 0.022348 | 0.042012 | 0.110022 | 0.128744 | 0.248665
roadNet-TX | 0.117129 | 0.065016 | 0.047048 | 0.034324 | 0.022388 | 0.026438 | 0.108113 | 0.035132 | 0.027658 | 0.052228 | 0.140249 | 0.154466 | 0.309297
soc-Epinions1 | 1.538742 | 0.876433 | 0.100463 | 0.048663 | 0.062346 | 0.019989 | 0.023260 | 0.051619 | 0.063603 | 0.043226 | 0.042753 | 0.021945 | 0.023399
wiki-Vote | 0.354843 | 0.189848 | 0.020137 | 0.010243 | 0.018043 | 0.005117 | 0.005159 | 0.009498 | 0.019525 | 0.013211 | 0.014798 | 0.005232 | 0.005956

TABLE II: Execution time (in seconds) for Intel Xeon Max 9480.
Key: IR: Itai-Rodeh. V: Vertex-iterator. VD: Vertex Iterator (direction-oriented). EM: Edge Iterator with MergePath. EMD: Edge Iterator with MergePath (direction-oriented). EB: Edge Iterator with BinarySearch. EBD: Edge Iterator with BinarySearch (direction-oriented). EP: Edge Iterator with Partitioning. EPD: Edge Iterator with Partitioning (direction-oriented). EH: Edge Iterator with Hashing. EHD: Edge Iterator with Hashing (direction-oriented). F: Forward. FH: Forward with Hashing. FHD: Forward with Hashing (degree-order). TS: Tri_simple (Davis) LA: Linear Algebra (CMU). CE: Cover Edge. CED: Cover Edge (degree-order). Bader: this paper. BaderD: this paper with degree-order. Graph | n | m | # triangles | IR | V | VD | EM | EMD | EB | EBD |  |  $k$ (%) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---
karate | 34 | 78 | 45 | 0.000084 | 0.000019 | 0.000007 | 0.000012 | 0.000006 | 0.000018 | 0.000009 |  | 35.9 |
RMAT 6 | 64 | 1024 | 9100 | 0.000653 | 0.001432 | 0.000291 | 0.000392 | 0.000192 | 0.000869 | 0.000426 |  | 93.8 |
RMAT 7 | 128 | 2048 | 18855 | 0.003678 | 0.005776 | 0.001651 | 0.002121 | 0.001065 | 0.004745 | 0.002365 |  | 90.9 |
RMAT 8 | 256 | 4096 | 39602 | 0.005814 | 0.009776 | 0.002655 | 0.003127 | 0.001569 | 0.007266 | 0.003583 |  | 87.6 |
RMAT 9 | 512 | 8192 | 86470 | 0.018371 | 0.030974 | 0.008197 | 0.008432 | 0.004211 | 0.017575 | 0.008738 |  | 87.2 |
RMAT 10 | 1024 | 16384 | 187855 | 0.058950 | 0.172546 | 0.026058 | 0.021977 | 0.010949 | 0.049523 | 0.024602 |  | 82.8 |
RMAT 11 | 2048 | 32768 | 408876 | 0.183945 | 0.342650 | 0.084153 | 0.058176 | 0.028950 | 0.116835 | 0.057881 |  | 81.1 |
RMAT 12 | 4096 | 65536 | 896224 | 0.566386 | 1.180451 | 0.290440 | 0.152799 | 0.076057 | 0.313237 | 0.155666 |  | 77.5 |
RMAT 13 | 8192 | 131072 | 1988410 | 1.855761 | 4.068261 | 0.960160 | 0.404467 | 0.202029 | 0.789813 | 0.392430 |  | 74.9 |
RMAT 14 | 16384 | 262144 | 4355418 | 6.005944 | 14.231056 | 3.411291 | 1.069533 | 0.532122 | 1.951912 | 0.968742 |  | 70.5 |
RMAT 15 | 32768 | 524288 | 9576800 | 20.030438 | 49.387592 | 11.505111 | 2.839230 | 1.412183 | 5.141348 | 2.544929 |  | 68.4 |
RMAT 16 | 65536 | 1048576 | 21133772 | 65.629646 | 171.271757 | 38.996294 | 7.518746 | 3.732511 | 12.724100 | 6.271381 |  | 65.5 |
RMAT 17 | 131072 | 2097152 | 46439638 | 375.735104 | 485.577535 | 135.059792 | 19.910985 | 9.883762 | 33.311904 | 16.416130 |  | 62.8 |
RMAT 18 | 262144 | 4194304 | 101930789 | 1268.171131 | 1659.316098 | 457.361748 | 53.163797 | 26.201594 | 85.430737 | 41.790449 |  | 60.3 |
amazon0302 | 262111 | 899792 | 717719 | 0.338818 | 0.355492 | 0.056826 | 0.135808 | 0.066465 | 0.192788 | 0.093958 |  | 44.2 |
amazon0312 | 400727 | 2349869 | 3686467 | 2.144190 | 1.417495 | 0.430188 | 0.734345 | 0.362226 | 1.036567 | 0.494136 |  | 52.4 |
amazon0505 | 410236 | 2439437 | 3951063 | 1.953721 | 1.543616 | 0.471659 | 0.774813 | 0.382143 | 1.106683 | 0.528466 |  | 52.7 |
amazon0601 | 403394 | 2443408 | 3986507 | 1.864989 | 1.531052 | 0.468426 | 0.771804 | 0.381114 | 1.110423 | 0.626398 |  | 52.8 |
loc-Brightkite | 58228 | 214078 | 494728 | 0.583671 | 0.603258 | 0.147395 | 0.125952 | 0.063082 | 0.191693 | 0.094928 |  | 43.2 |
loc-Gowalla | 196591 | 950327 | 2273138 | 5.787065 | 12.271734 | 3.931624 | 2.254498 | 1.122959 | 1.317039 | 0.641545 |  | 50.8 |
roadNet-CA | 1971281 | 2766607 | 120676 | 0.653579 | 0.078303 | 0.037398 | 0.106735 | 0.069202 | 0.114088 | 0.075968 |  | 14.5 |
roadNet-PA | 1090920 | 1541898 | 67150 | 0.361385 | 0.044707 | 0.021273 | 0.060422 | 0.039120 | 0.064219 | 0.042327 |  | 14.6 |
roadNet-TX | 1393383 | 1921660 | 82869 | 0.498325 | 0.052356 | 0.025527 | 0.072977 | 0.047387 | 0.077212 | 0.051569 |  | 14.0 |
soc-Epinions1 | 75888 | 405740 | 1624481 | 4.949491 | 6.610313 | 1.637538 | 0.670166 | 0.332638 | 1.226177 | 0.602162 |  | 53.3 |
wiki-Vote | 8297 | 100762 | 608389 | 0.564122 | 1.101121 | 0.191629 | 0.134719 | 0.067070 | 0.309990 | 0.154091 |  | 54.3 |
Graph | EP | EPD | EH | EHD | F | FH | FHD | TS | LA | CE | CED | Bader | BaderD
karate | 0.000034 | 0.000015 | 0.000009 | 0.000006 | 0.000004 | 0.000004 | 0.000008 | 0.000005 | 0.000002 | 0.000006 | 0.000009 | 0.000009 | 0.000011
RMAT 6 | 0.001014 | 0.000532 | 0.000071 | 0.000033 | 0.000034 | 0.000016 | 0.000017 | 0.000025 | 0.000027 | 0.000057 | 0.000046 | 0.000023 | 0.000023
RMAT 7 | 0.005489 | 0.002928 | 0.000398 | 0.000177 | 0.000230 | 0.000073 | 0.000081 | 0.000131 | 0.000204 | 0.000457 | 0.000358 | 0.000133 | 0.000120
RMAT 8 | 0.007966 | 0.004306 | 0.000511 | 0.000249 | 0.000367 | 0.000127 | 0.000126 | 0.000194 | 0.000338 | 0.000675 | 0.000551 | 0.000187 | 0.000199
RMAT 9 | 0.020866 | 0.011328 | 0.001285 | 0.000644 | 0.000981 | 0.000316 | 0.000318 | 0.000538 | 0.000905 | 0.001720 | 0.001442 | 0.000463 | 0.000477
RMAT 10 | 0.054240 | 0.029602 | 0.003113 | 0.001598 | 0.002603 | 0.000729 | 0.000703 | 0.001370 | 0.002384 | 0.004150 | 0.003601 | 0.001097 | 0.001032
RMAT 11 | 0.140766 | 0.077608 | 0.007638 | 0.003886 | 0.006698 | 0.001663 | 0.001579 | 0.003562 | 0.006106 | 0.009849 | 0.008694 | 0.002186 | 0.002306
RMAT 12 | 0.361722 | 0.201107 | 0.019090 | 0.009670 | 0.017082 | 0.003810 | 0.003632 | 0.008985 | 0.015445 | 0.023041 | 0.020660 | 0.004851 | 0.004978
RMAT 13 | 0.927790 | 0.519227 | 0.048198 | 0.024338 | 0.044297 | 0.008913 | 0.008062 | 0.022965 | 0.039156 | 0.054002 | 0.048318 | 0.010538 | 0.010336
RMAT 14 | 2.390258 | 1.350289 | 0.123571 | 0.061666 | 0.113511 | 0.020460 | 0.017647 | 0.059840 | 0.098365 | 0.124021 | 0.110538 | 0.023147 | 0.021745
RMAT 15 | 6.181050 | 3.463447 | 0.335935 | 0.164295 | 0.294636 | 0.049240 | 0.040570 | 0.167853 | 0.247720 | 0.291674 | 0.256692 | 0.052713 | 0.047445
RMAT 16 | 15.620494 | 8.921255 | 1.139298 | 0.552865 | 0.766895 | 0.123122 | 0.098112 | 0.528412 | 0.628183 | 0.687476 | 0.591732 | 0.127122 | 0.107139
RMAT 17 | 40.535918 | 23.082879 | 3.430538 | 1.699966 | 1.983156 | 0.334009 | 0.243371 | 1.475421 | 1.577658 | 1.602727 | 1.358685 | 0.336016 | 0.249839
RMAT 18 | 103.623609 | 58.983807 | 10.785311 | 5.093805 | 5.185930 | 0.929694 | 0.605976 | 5.027324 | 4.067794 | 3.904872 | 3.126732 | 0.936819 | 0.629180
amazon0302 | 0.301605 | 0.157618 | 0.064183 | 0.033356 | 0.024741 | 0.021114 | 0.042219 | 0.038521 | 0.023865 | 0.045608 | 0.066787 | 0.046098 | 0.065133
amazon0312 | 1.671686 | 0.947525 | 0.285707 | 0.139874 | 0.106593 | 0.075217 | 0.143323 | 0.159351 | 0.103863 | 0.152911 | 0.207114 | 0.137305 | 0.185652
amazon0505 | 1.780392 | 1.006270 | 0.296284 | 0.145469 | 0.112280 | 0.078005 | 0.150319 | 0.166425 | 0.109580 | 0.159629 | 0.217396 | 0.141835 | 0.192150
amazon0601 | 1.807190 | 1.005138 | 0.311293 | 0.145677 | 0.113539 | 0.079493 | 0.148641 | 0.176862 | 0.109842 | 0.165447 | 0.217130 | 0.144488 | 0.192724
loc-Brightkite | 0.285579 | 0.166176 | 0.028593 | 0.015042 | 0.012540 | 0.007266 | 0.010768 | 0.014710 | 0.012744 | 0.012909 | 0.016484 | 0.009446 | 0.013962
loc-Gowalla | 3.057021 | 2.229423 | 0.377311 | 0.187272 | 0.088885 | 0.040840 | 0.056879 | 0.195321 | 0.084664 | 0.079257 | 0.093252 | 0.049751 | 0.069627
roadNet-CA | 0.184792 | 0.103255 | 0.076952 | 0.056482 | 0.037726 | 0.044601 | 0.191125 | 0.059184 | 0.045363 | 0.095519 | 0.231007 | 0.141794 | 0.262101
roadNet-PA | 0.104778 | 0.058080 | 0.042658 | 0.031094 | 0.020907 | 0.024783 | 0.094690 | 0.032229 | 0.024773 | 0.048739 | 0.121119 | 0.070754 | 0.141447
roadNet-TX | 0.127673 | 0.071134 | 0.052878 | 0.039065 | 0.025792 | 0.030903 | 0.121140 | 0.040004 | 0.031081 | 0.062052 | 0.154108 | 0.088572 | 0.180140
soc-Epinions1 | 1.674840 | 0.955909 | 0.110867 | 0.054109 | 0.067796 | 0.021483 | 0.024809 | 0.058189 | 0.070127 | 0.047488 | 0.045225 | 0.023882 | 0.025212
wiki-Vote | 0.387609 | 0.207687 | 0.021763 | 0.011102 | 0.019645 | 0.005587 | 0.005645 | 0.010345 | 0.021255 | 0.014397 | 0.015981 | 0.005747 | 0.006269


# Position of the centroid of a planar convex body

MAREK LASSAK

Abstract. It is well known that any planar convex body $A$ permits to inscribe
an affine-regular hexagon $H_{A}$. We prove that the centroid of $A$ belongs
to the homothetic image of $H_{A}$ with ratio $\frac{4}{21}$ and the center in
the center of $H_{A}$. This ratio cannot be decreased.

Keywords: convex body, centroid, affine-regular hexagon

MSC: Primary: 52A10

##  1 Introduction

This paper concerns the position of the centroid of a planar convex body,
i.e., a closed bounded convex set. Recall that the notion of centroid is
discussed by, among others, Bonnesen and Fenchel [2], Grünbaum [3], Hammer [4]
and Neumann [5].

As usual, by an affine-regular hexagon we understand a non-degenerated affine
image of the regular hexagon. Besicovitch [1] proved that for every planar
convex body $A$ there exists an affine-regular hexagon $H_{A}$ inscribed in
$A$. Our aim is to prove that the centroid of $A$ belongs to the homothetic
image $\frac{4}{21}H_{A}$ of $H_{A}$ with ratio $\frac{4}{21}$ and the center
in the center of $H_{A}$. In general, this ratio cannot be lessened, which is
explained at the end of the paper.

For a compact set $C$ of the Euclidean plane $E^{2}$ denote by ${\rm
cen}_{x}(C)$ and ${\rm cen_{y}}(C)$ the first and the second coordinates of
the centroid of $C$. Let compact sets $B_{1},\dots,B_{n}\subset E^{2}$ with
non-empty interiors have disjoint interiors and $B=\bigcup_{j=1}^{n}B_{j}$. It
is well known that

${\rm cen}_{x}(B)=\frac{\Sigma_{j=1}^{n}{\rm cen}_{x}(B_{j})\cdot{\rm
area}(B_{j})}{\Sigma_{j=1}^{n}{\rm area}(B_{j})},\ \ \ {\rm
cen}_{y}(B)=\frac{\Sigma_{j=1}^{n}{\rm cen}_{y}(B_{j})\cdot{\rm
area}(B_{j})}{\Sigma_{j=1}^{n}{\rm area}(B_{j})}.$ $None$

##  2 The position of the centroid of a convex body with respect to an
inscribed affine-regular hexagon

Let $D\subset E^{2}$ and $\ell$ be a straight line. Imagine $D$ as the union
of segments (including one-point segments) being intersections of $D$ by
straight lines perpendicular to $\ell$. Shift every such a segment
perpendicularly to $\ell$ in order to obtain its image centered at $\ell$.
Denote the union of all these obtained segments by ${\rm sym}_{\ell}D$. It is
the result of the Steiner symmetrization of $D$. The proof of the following
lemma is given in a number of books. For instance in Section 40 of [2].

Lemma. If $D\subset E^{2}$ is convex, then ${\rm sym}_{\ell}D$ is convex.

Theorem. Let $A\subset E^{2}$ be a convex body and $H_{A}$ be an affine-
regular hexagon inscribed in $A$. Then the centroid of $A$ belongs to the
homothetic image of $H_{A}$ with ratio $\frac{4}{21}$ and center in the center
of $H_{A}$.

###### Proof.

For better clarity, we divide the proof into a preliminary text mostly on
notations, and then Parts 1–8 with considerations.

We do not lose the generality assuming that the successive vertices
$a_{1},\dots,a_{6}$ of $H_{A}$ are $(1,1)$, $(-1,1)$, $(-2,0)$, $(-1,-1)$,
$(1,-1)$, $(2,0)$, see Figure. Denote by $o$ the center $(0,0)$ and by $a$ the
midpoint of $a_{1}a_{2}$. Since we deal with ${{\rm cen_{y}}}(A)$, by Lemma we
may assume that $x=0$ is an axis of symmetry of $A$.

In order to prove the assertion, let us show that for any side of
$\frac{4}{21}H_{A}$ the centroid of $A$ is on the same side of the straight
line containing this side which contains $o$. Observe that it is enough to
show this for one side of the hexagon $\frac{4}{21}H_{A}$. Let us provide this
task for the side connecting $\frac{4}{21}a_{1}$ and $\frac{4}{21}a_{2}$.

Denote by $\overline{a}_{i}$ the intersection of the straight lines containing
$a_{i}a_{i+1}$ and $a_{i-1}a_{i-2}$ for $i=1,\dots,6$ (mod $6$), see Figure.
We define the star $S(H_{A})$ over $H_{A}$ as the union of $H_{A}$ and six
triangles $T_{i}(H_{A})=a_{i-1}{\buildrel-\over{a}_{i}}a_{i}$, where
$i=1,\dots,6$ and where $a_{0}$ means $a_{6}$. From the convexity of $A$ we
conclude that $A\subset S(H_{A})$.

We do not make our considerations narrower assuming that the centroid of $A$
is over or on the axis $y=0$. Since our aim is to show that ${{\rm
cen_{y}}}(A)\leq\frac{4}{21}$ for every convex body $A$, it is sufficient to
consider only such convex bodies $A$ which are disjoint with the interiors of
$T_{4}(H_{A})$, $T_{5}(H_{A})$ and $T_{6}(H_{A})$. Still the closure of
$A\setminus\bigcup_{i=4}^{6}T_{i}(H_{A})$ is a convex body with $H$ inscribed
and the centroid at the same or higher level.

Provide any supporting straight line $L_{1}$ of $A$ at $a_{1}$ and the
symmetric (with respect to $x=0$) supporting line $L_{2}$ of $A$ at $a_{2}$.
Denote by $u=(0,w)$ the intersection point of $L_{1}$ (and thus of $L_{2}$)
with the axis $x=0$. Since the second coordinates of $a$ and
$\overline{a}_{2}$ are equal to $1$ and $2$, respectively, we have
$w\in[1,2]$.

Since $L_{1}$ passes through $u=(0,w)$ and $a_{1}=(1,1)$, it has the equation
$y-1=(-w+1)(x-1)$. Its point of intersection with the segment
$a_{6}{\buildrel-\over{a}_{1}}$ (being a subset of the straight line $y=x-2$)
is $m_{1}=(\frac{2+w}{w},\frac{2-w}{w})$. Similarly, we get the symmetric
point $m_{2}$ being the intersection of $L_{2}$ with the segment
$a_{3}{\buildrel-\over{a}_{3}}$.

Figure. Illustration to the proof of Theorem

Later we explain the geometric meaning of the following number

$w_{0}=\frac{1}{3}({\root 3 \of{44-3\sqrt{177}}}+{\root 3
\of{44+3\sqrt{177}}}-1)=1.6589670....$

Parts 3–7 lead to the proof of our theorem for $w\in[w_{0},2]$ and Part 8 for
$w\in[1,w_{0}]$ .

Part 1 where we introduce a heptagon and find its ${\rm cen_{y}}$.

Let $z\in[0,1]$. Since $a_{1}=(1,1)$ and
$m_{1}=(\frac{2+w}{w},\frac{2-w}{w})$, every point $p_{1}(z)$, or shortly
$p_{1}$, of $a_{1}m_{1}$ has the form $(1-z)a_{1}+zm_{1}$. So
$p_{1}=((1-z)+z\frac{2+w}{w},(1-z)+z\frac{2-w}{w})=(z\cdot\frac{2}{w}+1,z\cdot\frac{2-2w}{w}+1)$.
The symmetric point with respect to $x=0$ is denoted by $p_{2}$. The second
coordinates of them are $z\cdot\frac{2-2w}{w}+1$.

Consider the heptagon $G=up_{2}a_{3}a_{4}a_{5}a_{6}p_{1}$. The area of each of
the two symmetric wings $W_{1}=a_{1}a_{6}p_{1}$ and $W_{2}=a_{2}a_{3}p_{2}$ of
$G$ is $z\cdot\frac{2-w}{w}$ and ${\rm cen_{y}}$ of each wing of this heptagon
is $\frac{1+z\frac{2-2w}{w}+1}{3}=\frac{2+z\frac{2-2w}{w}}{3}$. The area of
the triangle $a_{1}ua_{2}$ is $\frac{1}{2}\cdot 2\cdot(w-1)=w-1$ and its ${\rm
cen_{y}}$ is $\frac{2+w}{3}$. Moreover, the area of $H_{A}$ is $6$ and its
${\rm cen_{y}}$ is $0$. Taking all this into account and having in mind that
$G=H_{A}\cup a_{1}a_{6}p_{1}\cup a_{2}a_{3}p_{2}\cup a_{1}ua_{2}$, by the
right part of (1) we conclude that

${\rm
cen_{y}}(G)=\frac{0+\frac{2}{3}(2+z\frac{2-2w}{w})z\frac{2-w}{w}+\frac{2+w}{3}(w-1)}{6+2z\frac{2-w}{w}+w-1}$

which, after a simplification, equals to

$\frac{2(2+z\frac{2-2w}{w})z\frac{2-w}{w}+w^{2}+w-2}{6z\frac{2-w}{w}+3w+15}.\hskip
14.22636pt$ $None$

Part 2 whose aim is to show the following statement

Denote by $\nu$ the numerator and by $\delta$ the denominator of ${\rm
cen_{y}}(G)$ as in (2) (so ${\rm cen_{y}}(G)=\frac{\nu}{\delta}$). Consider a
truncation of the wings $W_{i}$ of $G$ to symmetric convex subsets
$A_{i}=W_{i}\cap A$ for $i=1,2$. Put $V_{i}=W_{i}\setminus A_{i}$ for $i=1,2$
and $V=V_{1}\cup V_{2}$. We have

$\frac{\nu-{\rm area}(V){\rm cen_{y}}(V)}{\delta-{\rm
area}(V)}\leq\frac{\nu}{\delta}\hskip 11.38092pt{\it iff}\hskip 11.38092pt{\rm
cen_{y}}(V)\geq\frac{\nu}{\delta}.$ $None$

Let us confirm this. We have $\frac{\nu-{\rm area}(V){\rm
cen_{y}}(V)}{\delta-{\rm area}(V)}\leq\frac{\nu}{\delta}$ iff $\delta(\nu-{\rm
area}(V){\rm cen_{y}}(V))\leq\nu(\delta-{\rm area}(V))$ iff $\nu\cdot{\rm
area}(V)\leq\delta\cdot{\rm area}(V){\rm cen_{y}}(V)$ iff
$\nu\leq\delta\cdot{\rm cen_{y}}(V)$ iff ${\rm
cen_{y}}(V)\geq\frac{\nu}{\delta}$.

Observe that $\frac{\nu-{\rm area}(V){\rm cen_{y}}(V)}{\delta-{\rm area}(V)}$
is nothing else but ${\rm cen_{y}}(A^{\prime})$, where $A^{\prime}=G\setminus
V$.

Part 3 where we start considerations for $w\in[w_{0},2]$.

For every $w\in[w_{0},2]$ we are looking for the positions of $p_{1}$ and thus
of $p_{2}$ such that ${\rm cen_{y}}(G)$ is the largest. For this reason let us
find the derivative of the function $(2)$ with respect to $z$:

$\frac{2(w-2)[4z^{2}(-w^{2}+3w-2)+4z(w^{2}+4w-5)+(w^{4}-w^{3}-12w^{2})]}{3w(w^{2}-2wz+5w+4z)^{2}}.$
$None$

The discriminant of the quadratic function in the square bracket is
$16w^{2}(2w^{4}+4w^{3}-w^{2}-6w+1)$. Hence (4) equals $0$ for
$z=\frac{w(w^{2}+4w-5\pm\sqrt{2w^{4}+4w^{3}-w^{2}-6w+1})}{2(w^{2}-3w+2)}$.
Take into account only the root

$z_{w}=\frac{w(w^{2}+4w-5-\sqrt{2w^{4}+4w^{3}-w^{2}-6w+1})}{2(w^{2}-3w+2)}$
$None$

which is positive for every $w\in[w_{0},2)$ (the other one is always negative
here). Moreover, put $z_{2}=\lim_{w\to 2^{-}}z_{w}$. This is
$z_{2}=\frac{5}{7}$.

We see that for any fixed $w\in[w_{0},2]$ the global maximum of $(2)$ as a
function of $z$ from the interval $[0,1]$ can be only for $z=0$, $z=z_{w}$ or
$z=1$. Substituting these three $z$ into $(2)$ we see that the global maximum
of (2) in the interval $[0,1]$ is at $z=z_{w}$ for every fixed
$w\in[w_{0},2]$.

Part 4 where our aim is to show that for each $w\in[w_{0},2]$ the value of (2)
for $z=z_{w}$ is at most $\frac{4}{21}$.

This task with substituting $z=z_{w}$ into (2) seems to be very complicated to
perform. We can get it around by performing the more general task to show that
for every $w\in[w_{0},2]$ and $z\in[\frac{5}{7},1]$ we have

$\frac{2(2+z\frac{2-2w}{w})z\frac{2-w}{w}+w^{2}+w-2}{6z\frac{2-w}{w}+3w+15}\leq\frac{4}{21}.$
$None$

This task is more general since $z_{w}$ belongs to $[\frac{5}{7},1]$ for every
$w\in[w_{0},2]$. Really, the inequality $z_{w}\leq 1$ is equivalent to
$w^{6}-7w^{4}-2w^{2}+16w^{2}+8w-16\geq 0$ and thus to
$(w-1)(w-2)(w+3)(w^{3}+w^{2}-2w-4)\geq 0$, which means that it holds true in
$[1,2]$ if and only if $w\in[w_{0},2]$ (still $w_{0}$ is the only real root of
this polynomial). Moreover, the inequality $\frac{5}{7}\leq z_{w}$ is
equivalent to $-7(w-2)(7w^{2}+22w+20)\geq 0$, which means that it holds true
in the whole interval $[1,2]$, so in particular for every $w\in[w_{0},2]$.

Equivalently to (6), it is sufficient to show that

$28z^{2}(w^{2}-3w+2)+20zw(2-w)+w^{2}(7w^{2}+3w-34)$ $None$

is at most $0$ for every point $(w,z)$ of the rectangle
$[w_{0},2]\times[\frac{5}{7},1]$.

In order to simplify evaluations consider this task in the larger rectangle
$[1,2]\times[\frac{5}{7},1]$.

Let us apply the following method of finding the global maximum of a
continuous function $f(w,z)$ in a polygon $R\subset E^{2}$. Namely, first we
find the points being the solutions of the system of two equations when
partial derivatives of our function $f(w,z)$ are $0$ in the interior of $R$.
Next we write the equations of the sides in the forms $z=g(w)$ or $w=g(z)$. We
find the critical points in the relative interiors of each side, where the
derivative of the respective equation is $0$. Finally, we check the values of
$f(w,z)$ at the vertices of $R$. The largest value at all the found points
gives the maximum value of $f(w,z)$ in $R$.

In our particular case our function
$f(w,z)=28z^{2}(w^{2}-3w+2)+20zw(2-w)+w^{2}(7w^{2}+3w-34)$ is given by (7).
Moreover, $R=[1,2]\times[\frac{5}{7},1]$. According to the recalled method we
find the partial derivatives
$f^{\prime}_{w}(w,z)=28w^{3}+9w^{2}+56wz^{2}-40wz-68w-84z^{2}+40z$ and
$f^{\prime}_{z}(w,z)=56w^{2}z-20w^{2}-168wz+40w+112z$. Consider the system of
equations when both are $0$. Finding $z$ from the second and substituting to
the first we get three solutions: $w\approx-1.8$, $w=0$ and $w\approx 1.544$.
None of them is in the interval $[w_{0},2]$. Hence the system of equations has
no solution in our $R$, and thus in its interior.

Let us find the critical points in the relative interiors of the sides. After
substituting $z=\frac{5}{7}$ to $f(w,z)$ we get
$\frac{1}{7}(49w^{4}+21w^{3}-238w^{2}-100w+200)$. Its derivative
$\frac{1}{7}(196w^{3}+63w^{2}-476w-100)$ is $0$ only at $w_{1}=1.5103...$.
Placing $z=1$ to our $f(w,z)$ we get $7w^{4}+3w^{3}-26w^{2}-44w+56$. Its
derivative $28w^{3}+9w^{2}-52w-44$ equals $0$ in $[1,2]$ only at
$w_{2}=1.5427...$. Substituting $w=1$ to $f(w,z)$ we get $20z-24$, which is
negative for every $z\in[\frac{5}{7},1]$. Placing $w=2$ to $f(w,z)$ we get $0$
for every $z\in[\frac{5}{7},1]$.

We have $f(w_{1},\frac{5}{7})\approx-23.803$, $f(w_{2},1)\approx-23.094$,
$f(1,1)=-4$, $f(1,\frac{5}{7})=-9.714$, $f(2,\frac{5}{7})=0$, and $f(2,1)=0$.
Thus the global maximum of $f(w,z)$ in $R$ is $0$. Hence (7) is at most $0$
and thus (6) holds true in $R$. We conclude that (2) for $z=z_{w}$ is at most
$\frac{4}{21}$ for every $w\in[1,2]$ and so for every $w\in[w_{0},2]$.

Part 5 where we show that ${\rm cen_{y}}(V)\geq\frac{\nu}{\delta}$ for any
$w\in[w_{0},2]$ and $z_{w}$ in place of $z$.

Recall from Part 2 that $\frac{\nu}{\delta}={\rm cen_{y}}(G)$. Looking at the
second coordinates of $a_{1},a_{6}$ and $p_{1}$ we get ${\rm
cen_{y}}(a_{1}a_{6}p_{1})=(z_{w}\frac{2-2w}{w}+1)/2$. Hence ${\rm
cen_{y}}(V_{1})\geq(z_{w}\frac{2-2w}{w}+1)/2$ and so ${\rm
cen_{y}}(V)\geq(z_{w}\frac{2-2w}{w}+1)/2$.

We see that in order to confirm the promise of Part 5 it is sufficient to show
that

$\frac{z_{w}\frac{2-2w}{w}+1}{2}\leq\frac{2(2+z_{w}\frac{2-2w}{w})z_{w}\frac{2-w}{w}+w^{2}+w-2}{6z_{w}\frac{2-w}{w}+3w+15},$
$None$

for every $w\in[w_{0},2]$, where the right side is taken from (2). Instead,
let us show the inequality

$\frac{z\frac{2-2w}{w}+1}{2}\leq\frac{2(2+z\frac{2-2w}{w})z\frac{2-w}{w}+w^{2}+w-2}{6z\frac{2-w}{w}+3w+15},$

or equivalently, let us show that

$8z^{2}-12z^{2}w-22zw^{2}+26zw+4z^{2}w^{2}-6zw^{3}-2w^{4}+w^{3}+19w^{2}$
$None$

is at most $0$ for every point $(w,z)$ of the piece of the curve $z=z_{w}$
when $w\in[w_{0},2]$.

Instead, let us find the global maximum of (9) in a triangle containing it.
Namely, in the triangle $T$ between the straight lines $w=2$,
$z=-\frac{5}{7}w+\frac{15}{7}$, and $z=1$. Its vertices are $(2,1)$,
$(\frac{8}{5},1)$ and $(2,\frac{13}{21})$.

First let us show that the piece of the curve $z=z_{w}$ for $w\in[w_{0},2]$ is
a subset of $T$. The reason is that $-\frac{5}{7}w+\frac{15}{7}\leq z_{w}\leq
1$ for every $w\in[w_{0},2]$. The left inequality is equivalent to the
inequality $(2839w^{4}-10571w^{3}+18960w^{2}-284088w+22472)(w-1)(2-w)\geq 0$
which holds true for every $w\in(-\infty,\infty)$. Thus in $[1,2]$ and so for
every $w\in[\frac{8}{5},2]$. The right inequality $z_{w}\leq 1$ is shown just
after (6).

Next let us find the global maximum of (9) in $T$ by the method described in
Part 4.

Consider the system of equations
$-8w^{3}-18w^{2}z+3w^{2}+8wz^{2}-44wz+38w-12z^{2}+26z=0$ and
$-6w^{3}+8w^{2}z-22w^{2}-24wz+26w+16z=0$ (where the left sides are the partial
derivatives of (9)). Finding $z=\frac{3w^{3}+11w^{2}-13w}{4w^{2}-12w+8}$ from
the second and substituting it into the first we get the equation
$w(68w^{6}-141w^{5}-262w^{4}+359w^{3}+356w^{2}-447w+68)=0$ whose solutions are
$w=0,w\approx 0.183,w\approx 0.951,w\approx 1.037$ and $w\approx 2,614$. All
these $w$ are out of the interval $[\frac{8}{5},2]$ which implies that all the
obtained points $(w,z)$ are out of $T$. Thus the system of equations has no
solution in the interior of $T$.

Look for critical points in the relative interiors of the sides. Substituting
$z=-\frac{5}{7}w+\frac{15}{7}$ into (9) we get
$\frac{1}{49}(212w^{3}-511w^{2}-789w+1830)$. Its derivative
$\frac{1}{49}(848w^{3}-1533w^{2}-1578w+1830)$ is never $0$ in
$[\frac{8}{5},2]$. Putting $z=1$ into (9) we get $-2w^{4}-5w^{3}+w^{2}+22w$.
Its derivative $-8w^{3}-15w^{2}+2w+22$ is never $0$ in $[\frac{8}{5},2]$.
Putting $w=2$ into (9) we get $8z^{2}-84z+52$. Its derivative $16z-84$ is
never $0$ in $[\frac{5}{7},1]$.

The value of (9) at $(2,1)$ is $-44$, at $(\frac{8}{5},1)$ is $-11.827...$,
and at $(2,\frac{13}{21})$ is $-4.598...$. So the global maximum of the
function (9) in $T$ is $-11.827...$. Hence (9) is always negative in $T$.

Consequently, we have shown that (9) is at most $0$ in $T$ and thus that (8)
is true for every $w\in[w_{0},2]$. Therefore ${\rm
cen_{y}}(V)\geq\frac{\nu}{\delta}$ for $G$ with $z_{w}$ in the part of $z$.

Part 6 where we show that ${\rm cen_{y}}(A^{\prime})\leq\frac{4}{21}$ for
$w\in[w_{0},2]$.

Recall that ${\rm cen_{y}}(G)=\frac{\nu}{\delta}$. By Part 5 and by (3) we
have $\frac{\nu-{\rm area}(V){\rm cen_{y}}(V)}{\delta-{\rm
area}(V)}\leq\frac{\nu}{\delta}$. The left side is ${\rm cen_{y}}(A^{\prime})$
and the right one is ${\rm cen_{y}}(G)$ with $G$ is taken for $z=z_{w}$. By
(6) it is at most $\frac{4}{21}$. So ${\rm
cen_{y}}(A^{\prime})\leq\frac{4}{21}$.

Part 7 on enlarging $A^{\prime}$ up to $A$ which leads to the proof of our
theorem for $w\in[w_{0},2]$.

Put $A_{1}^{\prime\prime}=A\cap p_{1}a_{6}m_{1}$, $A_{2}^{\prime\prime}=A\cap
p_{2}a_{3}m_{2}$ and $A^{\prime\prime}=A_{1}^{\prime\prime}\cup
A_{2}^{\prime\prime}$. Clearly $A=A^{\prime}\cup A^{\prime\prime}$. We intend
to show that adding $A^{\prime\prime}$ to $A^{\prime}$ does not increase ${\rm
cen_{y}}$, so that ${\rm cen_{y}}(A)\leq{\rm cen_{y}}(A^{\prime})$.

First let us show that if the triangles $p_{1}a_{6}m_{1}$ and
$p_{2}a_{3}m_{2}$ are added to $A^{\prime}$, then ${\rm cen_{y}}$ does not
increase. Applying the easy to show implication: “if ${\rm int}(X)\cap{\rm
int}(Y)=\emptyset$, ${\rm cen_{y}}(X)\leq\mu$ and ${\rm cen_{y}}(Y)\leq\mu$,
then ${\rm cen_{y}}(X\cup Y)\leq\mu$ as well” and having in mind that ${\rm
cen_{y}}(A^{\prime})\leq\frac{4}{21}$ (see Part 6), it is sufficient to show
that ${\rm cen_{y}}(p_{1}a_{6}m_{1})\leq\frac{4}{21}$ (then also ${\rm
cen_{y}}(p_{2}a_{3}m_{2})\leq\frac{4}{21}$). Let us show this. Since ${\rm
cen_{y}}(p_{1}a_{6}m_{1})=(z_{w}\cdot\frac{2-2w}{w}+1+\frac{2-w}{w})/3$, we
have to show that this is at most $\frac{4}{21}$. This task is equivalent to
$7z_{w}(2-2w)\leq 4w-14$. After substituting $z_{w}$ and providing some
simplifications, this inequality is equivalent to $h(w)\geq 0$, where
$h(w)=49w^{6}-196w^{5}+105w^{4}+1946w^{2}+1800w-400$. We have
$h^{\prime\prime}(w)=14(105w^{4}-280w^{3}+90w^{2}+278)$. From the fact that
$h^{\prime\prime}(w)$ always positive we conclude that $h^{\prime}(w)$ is an
increasing function. Thus from $h(1)=3304$ we see that $h(w)\geq 0$ for $w\geq
1$, and thus for every $w\in[w_{0},2]$. Hence ${\rm
cen_{y}}(p_{1}a_{6}m_{1})\leq\frac{4}{21}$.

Also for adding only $A^{\prime\prime}$ to $A^{\prime}$, the value of ${\rm
cen_{y}}$ does not increase. The reason is that ${\rm
cen_{y}}(A_{1}^{\prime\prime})\leq{\rm cen_{y}}(p_{1}a_{6}m_{1})$ and ${\rm
cen_{y}}(A_{2}^{\prime\prime})\leq{\rm cen_{y}}(p_{2}a_{3}m_{2})$. The first
follows from the convexity of $A_{1}^{\prime\prime}$ and from the observation
that every segment jointing $a_{6}$ with a point of $p_{1}m_{1}$ has in common
with $A_{1}^{\prime\prime}$ only a segment which is lower. Analogously, we
confirm the second inequality.

We conclude that ${\rm cen_{y}}(A)\leq{\rm cen_{y}}(A^{\prime})$. This and
${\rm cen_{y}}(A^{\prime})\leq\frac{4}{21}$ (see Part 6) imply ${\rm
cen_{y}}(A)\leq\frac{4}{21}$.

Part 8 where we prove our theorem for $w\in[1,w_{0}]$.

Consider the pentagon $P=m_{1}um_{2}a_{4}a_{5}$. It is the special case of $G$
for $z=1$. Thus substituting $z=1$ to (2) we see that ${\rm cen_{y}}(P)$
equals to $\frac{w^{4}+w^{3}-2w^{2}-4w+8}{3w(w^{2}+3w+4)}$. In order to show
that this is at most $\frac{4}{21}$ for every $w\in[1,w_{0}]$ take into
account the equivalent inequality $(w-2)(7w^{3}+17w^{2}+8w-28)\leq 0$. Its
left side equals $0$ only for $w=2$ and $w=w_{3}\approx 0.934$. Consequently,
this inequality and thus also the preceding one hold true in $[w_{3},2]$.
Hence also in $[1,w_{0}]$. Resuming, ${\rm cen_{y}}(P)\leq\frac{4}{21}$.

From $z=1$ we see that $V_{1}=a_{1}a_{6}m_{1}$ for our $P=G$. The second
coordinates of $a_{1},a_{6}$ and $m_{1}$ give ${\rm
cen_{y}}(a_{1}a_{6}m_{1})=\frac{4-2w}{3w}$. Hence ${\rm
cen_{y}}(V_{1})\leq\frac{4-2w}{3w}$. Thus by ${\rm cen_{y}}(V)={\rm
cen_{y}}(V_{1})$ we get ${\rm cen_{y}}(V)\leq\frac{4-2w}{3w}$.

In order to show that the right side of (3) is now true we have to show that
${\rm cen_{y}}(V)\geq{\rm cen_{y}}(P)$, where, as $P$ takes the role of $G$,
the right side is denoted by $\frac{\nu}{\delta}$ in (3). Hence we have to
show that $\frac{4-2w}{3w}\geq\frac{w^{4}+w^{3}-2w^{2}-4w+8}{3w(w^{2}+3w+4)}$.
This is equivalent to the inequality $w^{4}+3w^{3}-8w-8\leq 0$. A simple
evaluation confirms that it is true in $[1,w_{0}]$ (by the way, we have here
the equality just for $w=w_{0}$). Thus ${\rm cen_{y}}(V)\geq{\rm cen_{y}}(P)$.

The shown inequality means that the right side of (3) is fulfilled. Hence the
left side of (3), i.e., ${\rm cen_{y}}(A^{\prime})\leq\frac{\nu}{\delta}$
holds true. From $A=A^{\prime}$ for our $P=G$ we obtain ${\rm
cen_{y}}(A)\leq\frac{\nu}{\delta}$. Consequently, from
$\frac{\nu}{\delta}={\rm cen_{y}}(P)\leq\frac{4}{21}$ we conclude that ${\rm
cen_{y}}(A)\leq\frac{4}{21}$.

Thanks to results of Parts 7 and 8 the thesis of our theorem holds true. ∎

The ratio $\frac{4}{21}$ in Theorem cannot be lessened as it follows from the
example of the pentagon ${\buildrel-\over{a}_{2}}a_{3}a_{4}a_{5}a_{6}$ in the
part of $A$, and the hexagon $a_{1}\dots a_{6}$ as $H_{A}$. The author expects
that there are no more such examples besides the affine images of the above
presented one.

## References

  * [1] A. S. Besicovitch, Measure of asymmetry of convex curves, J. London Math. Soc. 23, 247–240 (1948)
  * [2] T. Bonnesen and W. Fenchel, Theorie der konvexen Körper, Springer, Berlin, 1934. English translation: Theory of convex bodies, BBC Associates, Moscow, Idaho USA, 1987
  * [3] B. Grünbaum, Measures of symmetry of convex sets, Convexity, Proc. Sympos. Pure Math., vol. 7, Amer. Math. Soc., Providence, R.I., 1963, pp, 233–270
  * [4] P. C. Hammer, The centroid of a convex body, Proc. Amer. Math. Soc. 2, 522–525 (1951)
  * [5] B. H. Neumann, On some affine invariants of closed convex regions, J. London Math. Soc. 14, 262–272 (1939)

Marek Lassak

University of Science and Technology

85-789 Bydgoszcz

Poland

e-mail<EMAIL_ADDRESS>