✦ LIBER ✦

On large distances in planar sets

✍ Scribed by Katalin Vesztergombi

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 383 KB
Volume: 67
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90027-6

No coin nor oath required. For personal study only.

✦ Synopsis

Let n k denote the number of times the kth largest distance occurs among a set S of n points in the Euclidean plane. We prove that n2 ~< 2~n for arbitrary set S. This upper bound is sharp.

We consider the set S of n arbitrary points in R 2. We denote the largest distance between two points in S by dl, the second largest by d2. Let us denote by nl resp. n2 the number of distances equal to dl resp. d2. It was proven by Hopf and Pannwitz [1] and Sutherland [2]: Definition. We call a configuration of Fig. 1 a forbidden N.

📜 SIMILAR VOLUMES

The two largest distances in finite plan

The two largest distances in finite planar sets

✍ Katalin Vesztergombi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 333 KB

We determine all homogenous linear inequalities satisfied by the numbers of occurrences of the two largest distances among n points in the plane.

Maximum planar sets that determine k dis

Maximum planar sets that determine k distances

✍ Paul Erdős; Peter Fishburn 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 506 KB

Maximum planar sets that determine k distances are identified for k ~< 5. Evidence is presented for the conjecture that all maximum sets for k >~ 7 are subsets of the triangular lattice.

On the distribution of distances in fini

On the distribution of distances in finite sets in the plane

✍ K Vesztergombi 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 894 KB

Let n k denote the number of times the kth largest distance occurs among a set S of n points. We show that if S is the set of vertices of a convex polygone in the euclidean plane, then n1+2n2~3n and n2<~n +n 1. Together with the well-known inequality n~<~n and the trivial inequalities n~>~O and n2>~

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

An algorithm for finding a large indepen

An algorithm for finding a large independent set in planar graphs

✍ Norishige Chiba; Takao Nishizeki; Nobuji Saito 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 333 KB 👁 1 views

On large sets of Pk-decompositions

✍ Yanfang Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB 👁 1 views

Let G ¼ ðVðGÞ; EðGÞÞ be a graph. A ðv v v; G; Þ-GD is a partition of all the edges of LGD. In this paper, we obtain a general result by using the finite fields, that is, if q ! k ! 2 is an odd prime power, then there exists a ðq; P k ; k À 1Þ-LGD.