Rederiving the Upper Bound for Halving Edges using Cardano's Formula

2018/02/11 by Pintu Chauhan, Chauhan, Pintu, Manjish Pal +3
Computer Science · Mathematics · #Algorithms and Data Compression #Coding theory and cryptography #Computational Geometry (cs.CG) #FOS: Computer and information sciences #G.2.1 #I.3.5 #advanced mathematical theories

paper · pdf · doi:10.48550/arxiv.1802.03730

openalex publication_date 2018/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we rederive an old upper bound on the number of halving edges present in the halving graph of an arbitrary set of n points in 2-dimensions which are placed in general position. We provide a different analysis of an identity discovered by Andrejak et al, to rederive this upper bound of O(n^4/3). In the original paper of Andrejak et al. the proof is based on a naive analysis whereas in this paper we obtain the same upper bound by tightening the analysis thereby opening a new door to derive these upper bounds using the identity. Our analysis is based on a result of Cardano for finding the roots of a cubic equation. We believe that our technique has the potential to derive improved bounds on the number of halving edges.

Related

• Halving by a Thousand Cuts or Punctures
• A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length
• Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]
• The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
• Upper bounds on the extremal number of the 4-cycle