Dense Point Sets with Many Halving Lines
- PDF / 507,103 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 205 Views
Dense Point Sets with Many Halving Lines István Kovács1
· Géza Tóth2
Received: 4 April 2017 / Revised: 27 November 2018 / Accepted: 27 January 2019 © The Author(s) 2019
Abstract A planar point set of n points is called γ -dense if the ratio of the largest and smallest √ n. We construct a dense set of n points distances among the points is at most γ √ ( log n) in the plane with ne halving lines. This improves the bound (n log n) of Edelsbrunner et al. (Discrete Comput Geom 17(3):243–255, 1997). Our construction can be generalized to higher dimensions, for any d we construct a dense point set √ of n points in Rd with n d−1 e( log n) halving hyperplanes. Our lower bounds are asymptotically the same as the best known lower bounds for general point sets. Keywords Dense point set · Halving line · k-set
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach István Kovács: Supported by the National Research, Development and Innovation Office, NKFIH, K-111827 and by the New National Excellence Program of the Hungarian Ministry of Human Resources, UNKP-16-3-I. Géza Tóth: Supported by the National Research, Development and Innovation Office, NKFIH, K-111827. This work is connected to the scientific program of the “Development of quality-oriented and harmonized R+D+I strategy and functional model at BME” project, supported by the New Hungary Development Plan (Project ID: TÁMOP-4.2.1/B-09/1/KMR-2010-0002). István Kovács [email protected] Géza Tóth [email protected] 1
Budapest University of Technology and Economics, Budapest, Hungary
2
Alfréd Rényi Institute of Mathematics and Budapest University of Technology and Economics, Budapest, Hungary
123
Discrete & Computational Geometry
1 Introduction Let P be a set of n points in the plane in general position, that is, no three of them are on a line. A line, determined by two points of P, is a halving line if it has exactly (n −2)/2 points of P on both sides. Let f (n) denote the maximum number of halving lines that a set of n points can have. It is a challenging unsolved problem to determine f (n). The first bounds are due to Lovász [8], and Erd˝os et al. [6]. They established the upper bound O(n 3/2 ), and the lower bound (n log n) (see also [5] for a different lower bound construction). Despite great interest in this problem, there was no progress until the very small improvement due to Pach et al. [10]. They improved the upper bound to O(n 3/2 / log∗ n). The iterated logarithm of n, log∗ n, is the number of times the log function must be iteratively applied before the result is at most 1. The best known upper bound√ is O(n 4/3 ), due to Dey [3]. The lower bound has been improved by Tóth [13] to ne( log n) . Nivasch [9] simplified the construction of Tóth. Suppose that γ > 0. A planar point set P of n points is called γ -dense √ if the ratio of the largest and smallest distances determined by P is at most γ n. There exist arbitrarily large γ -dense point sets if and only if √ 2 3 γ ≥ , π see [4,7]. Dense point sets are important in the analysis of som
Data Loading...
