Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On distinct distances from a vertex of a convex polygon
Dumitrescu A.  Computational geometry (Proceedings of the twentieth annual symposium on computational geometry, New York, NY, Jun 8-11, 2004)57-60.2004.Type:Proceedings
Date Reviewed: Aug 4 2004

Paul Erdös first introduced the general topic of this paper in 1946 [1]. That topic was how to determine the minimum number of distinct distances determined by n points in the plane. The author looks at a variant of this problem where the points are in convex position. More specifically, the author proves that, given a set ρ of n points in convex position in the plane, there exists a point ρ, an element of ρ, such that the number of distinct distances from ρ is at least ⌈(13n-6)/36⌉. The previous best lower bound was ⌈n/3⌉, by Leo Moser in 1952 [2].

The paper begins the proof for the new lower bound by reviewing previous work. One of the keys is Moser’s lemma [2], which says, given a set of points in convex position inside a closed cap of a disk, all have distinct distances from any specific point. The author builds on this by first looking at a disk with three caps defined by three chords, where all convex points exist within the three caps. This allows the author to focus only on points within a single cap. He then counts all distinct distances within the cap from ρ, by counting the number of distinct concentric circles centered at ρ, where all other points exist on the circles’ boundaries. Any circle with two or more points on its boundary makes up one or more isosceles triangles determined by ρ. The author then uses the upper and lower bounds on the number of possible isosceles triangles to tighten the overall lower bound on the number of distinct distances, which leads to his final lower bound value.

Overall, the author does a great job of proving a very interesting theorem. However, the audience for this paper will be very specialized, since the reader will need some understanding of convexity theory and combinatorics to fully appreciate the proofs and overall design of the argument.

Reviewer:  Jeriad Zoghby Review #: CR129959 (0502-0256)
1) Erdvs, P. On sets of distances of points. , (1946), 248250.
2) Moser, L. On different distances determined by points. , (1952), 8591.
Bookmark and Share
  Featured Reviewer  
 
Counting Problems (G.2.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Counting Problems": Date
Enumeration of polyominoes using MACSYMA
Delest M. (ed) Theoretical Computer Science 79(1): 209-226, 1991. Type: Article
Nov 1 1992
On counting lattice points in polyhedra
Dyer M. SIAM Journal on Computing 20(4): 695-707, 1991. Type: Article
Aug 1 1992
Partially ordered sets and sorting
Atkinson M.  Computers in mathematical research (, Cardiff, Wales,1761988. Type: Proceedings
May 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy