Loading...
Please wait, while we are loading the content...
Similar Documents
SERIE B INFORMATIK Point Sets with Distinct Distances
| Content Provider | Semantic Scholar |
|---|---|
| Author | Thiele, Torsten |
| Copyright Year | 2009 |
| Abstract | For positive integers d and n let fd n denote the maximum cardinality of a subset of the n grid f ng with distinct mutual euclidean distances Improving earlier results of Erd os and Guy it will be shown that f n c n and for d that fd n cd n lnn where c cd are constants Also improvements of lower bounds of Erd os and Alon on the size of Sidon sets in f n g are given Furthermore it will be proven that any set of n points in the plane contains a subset with distinct mutual distances of size c n and for point sets in general position i e no three points on a line of size c n with constants c c To do so it will be shown that for n points in R with distinct distances d d dt where di has multiplicity mi one has Pt i m i c n for a positive constant c If the n points are in general position then we prove Pt i m i c n for a positive constant c and this bound is tight This con rms a conjecture of Erd os and Fishburn Moreover we give an e cient sequential algorithm for nding a subset of a given set with the desired properties for example with distinct distances of size as guaranteed by the probabilistic method under a more general setting Universit at Dortmund Fachbereich Informatik LS II D Dortmund Germany Freie Universit at Berlin Institut f ur Mathematik II Arnimallee D Berlin Germany E mail thiele math fu berlin de Introduction In EG Erd os and Guy considered the following problem Determine the maximum size of a subset X of the n n grid that is the set f ng f ng such that all mutual euclidean distances between di erent points of X are distinct compare also Gu Denoting the cardinality of such a set X by f n they proved the following Theorem EG For every integer n n c ln ln n f n c n lnn where c c are constants To obtain the lower bound for f n Erd os and Guy used Greedy type arguments The upper bound for f n follows from a result of Landau La namely that the number of integers less than x which are representable as a sum of two squares is asymptotically c x lnx where c is a positive constant Recently in Th by using more re ned counting techniques the lower bound from has been improved Theorem Th For all integers n f n c n lnn where c is a constant In this paper we will further improve the lower bound on f n by using uncrowded hypergraphs cf AKPSS and ALR as well as some results from number theory namely we will show Theorem For integers n f n c n where c is a constant In order to prove this we will show a so called anti Ramsey theorem which will be given in Section This anti Ramsey result together with some number theoretic results which we deduce in Section also yields lower bounds for the analog of the problem of Erd os and Guy in higher dimensions Let fd n denote the maximum size of a subset X of the d dimensional grid f ngd such that all mutual euclidean distances within X are distinct We remark that for d one has f n p n by using perfect di erence sets cf EG For d Erd os and Guy showed the following Theorem EG Let d be a positive integer and a xed real Then for positive integers n su ciently large n fd n c p d n where c is a constant Point Sets With Distinct Distances Indeed in EG it has been conjectured that fd n c d n lnn for d In Section we improve the lower bound on fd n Theorem Let d be a positive integer Then for every integer n fd n cd n ln n where cd is a constant only dependent on d In Section we will consider the corresponding selection problems for points in the plane in arbitrary position We will show that every n point set in the euclidean plane R contains a subset X with mutual distinct distances such that jX j c n for some constant c This improves a former result from Th where the lower bound c n has been shown Moreover we will show that under the assumption that the n points are in general position no three on a line the lower bound on jX j can be improved to c n To do so we will prove a conjecture of Erd os and Fishburn Fi EF Namely we will show the following if n points in general position in R are given with distinct distances d d dt where di occurs with multiplicity mi i t then Pt i m i c n for some positive constant c The regular n gon shows that this bound is tight up to a constant factor Moreover we will show that for the corresponding problem for n arbitrary points in R one has Pt i m i c n where c is a positive constant In Section we will give the new lower bound c n c a positive constant on the size of a B subset of the set f n g This improves earlier results of Alon and Erd os AE Finally in Section we consider some algorithmic aspects of these selection problems under a more general setting In particular using derandomization we will give an e cient sequential algorithm that nds in every edge coloring of the complete graph Kn a totally multicolored complete subgraph of size at least as large as guaranteed by the probabilistic method This algorithm has running time O n lnn P im i where mi is the number of edges in color i An Anti Ramsey Result In this section we will prove a so called anti Ramsey theorem which we will use for the proofs of Theorems and Before stating it we will introduce some notation For further references to anti Ramsey results we refer to ALR A graph G with vertex set V and edge set E is denoted by G V E By Kn we denote the complete graph on n vertices A mapping f E Kn T is called an edge coloring of Kn with colors t T For t T f t is the set of all edges colored by color t By dt jf t j n we denote the average degree of color t T Let dt be the maximum degree of color t i e the maximum number of edges in color t incident at some vertex and let max fdt j t Tg Finally a complete subgraph Kk of Kn is called totally multicolored if the restriction f jE Kk to the edge set of Kk is a one to one coloring Theorem For every there exists a constant C C such that for all integers n the following holds Let f E Kn T be a coloring and suppose satis es the following conditions |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://edocs.fu-berlin.de/docs/servlets/MCRFileNodeServlet/FUDOCS_derivate_000000000273/1994_16.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
