Iterative processes generating dense point sets
Except where reference is made to the work of others, the work described in this thesis
is my own or was done in collaboration with my advisory committee. This thesis does
not include proprietary or classifled information.
Gergely Ambrus
Certiflcate of Approval:
Krystyna M. Kuperberg
Professor
Mathematics and Statistics
Andr?as Bezdek, Chair
Professor
Mathematics and Statistics
Gary F. Gruenhage
Professor
Mathematics and Statistics
Christopher A. Rodger
Professor
Mathematics and Statistics
Stephen L. McFarland
Acting Dean
Graduate School
Iterative processes generating dense point sets
Gergely Ambrus
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
May 11, 2006
Iterative processes generating dense point sets
Gergely Ambrus
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Gergely Ambrus, son of Imre Ambrus and Judit (B?alint) Ambrus was born on May 1,
1983, in Budapest, Hungary. He graduated from the Radn?oti Mikl?os Experimental
Grammar School in Szeged, Hungary with Summa Cum Laude in 2001. He has been
attending the University of Szeged, Hungary on Mathematics major since 2001. He will
graduate from the University of Szeged with a Diploma in Mathematics in June, 2006. In
September, 2004 he entered the Graduate School at Auburn University on Mathematics
major.
iv
Thesis Abstract
Iterative processes generating dense point sets
Gergely Ambrus
Master of Science, May 11, 2006
44 Typed Pages
Directed by Andr?as Bezdek
The central problem of the thesis is the question of denseness of certain sets of
points in the plane. All of the following results are joint with A. Bezdek. We consider
point sets P, not a subset of a line, having the property that for every three noncollinear
points in P, a speciflc triangle center (incenter (IC), circumcenter (CC), orthocenter
(OC) resp.) is also in the set P. In Chapter 2, we generalize and solve the CC problem
in higher dimensions. We prove that if a point set P ? En has the property that for
each simplex of P the circumcenter of the simplex also belongs to P, then it is dense
in the whole space. Chapter 3 contains the solution of the OC problem in the plane,
essentially proving that P is either a dense point set of the plane or it is a subset of a
rectangular hyperbola. In the latter case, it is either a dense subset or it is a special
discrete subset of a rectangular hyperbola, for which we give both an algebraic and a
geometric characterization.
v
Acknowledgments
The author would like to thank his co-authors Dr. Andr?as Bezdek and Dr. Ferenc
Fodor for their valuable contributions and their assistance, which made it possible for
him to pursue his studies at Auburn University. He is also grateful for his family members
Judit, Imre and P?eter for their continuous support throughout the course of investigation.
vi
Style manual or journal used Journal of Approximation Theory (together with the
style known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally
LATEX) together with the departmental style-flle aums.sty.
vii
Table of Contents
List of Figures ix
1 Introduction and research overview 1
1.1 Transversal problem for higher dimensional unit balls . . . . . . . . . . . 1
1.2 Problems on iterative processes . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Higher dimensional circumcenter problem 6
3 Planar orthocenter problem 14
3.1 Review of elementary properties of hyperbolas . . . . . . . . . . . . . . . 14
3.2 Outline of the proof of Theorem 3.0.3 . . . . . . . . . . . . . . . . . . . . 16
3.3 If P has a convergent subsequence on the hyperbola H, then P is a dense
set of H. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Geometric characterization of inflnite, discrete and orthocentrically closed
sets of a rectangular hyperbola . . . . . . . . . . . . . . . . . . . . . . . . 19
3.5 Existence and algebraic characterization of the inflnite, discrete and or-
thocentrically closed sets of the rectangular hyperbola . . . . . . . . . . . 24
3.6 If P is not on the hyperbola, then it is a dense set of the plane. . . . . . . 28
Bibliography 34
viii
List of Figures
3.1 The case of a convergent sequence . . . . . . . . . . . . . . . . . . . . . . 18
3.2 The set is closed under the projection ?ij . . . . . . . . . . . . . . . . . . 21
3.3 Inductive steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 A point outside the hyperbola is generating a dense set . . . . . . . . . . 31
ix
Chapter 1
Introduction and research overview
During the period spent at Auburn University two new publications have been
written jointly with my supervisors Andr?as Bezdek (Auburn University) and Ferenc
Fodor (University of Szeged). Both of the investigated questions belong to Discrete
Geometry. The flrst article [1] was prepared in the Fall Semester of 2004 as a joint work
with A. Bezdek and F. Fodor, and later it won a 3rd Prize at the Hungarian Student
Paper Contest in 2005. It was also awarded as the Best Student Paper Presentation
of the 12th SCMA Conference in 2005. The second paper [2] was written in the Fall
Semester of 2005, jointly with A. Bezdek. This second paper provides the frame of the
thesis.
In the rest of this chapter we shall give a brief outline of the above mentioned two
papers together with a small historical overview.
1.1 Transversal problem for higher dimensional unit balls
A line l is a transversal to a family F of sets if l intersects every element of F. If
there is a line that intersects every member of the family F, then we say that F has the
property T. If every k or fewer members of F have a transversal then F has property
T(k).
In 1958, Gr?unbaum [9] conjectured that for a family of pairwise disjoint translates
of a convex disk T(5) ) T. The special case of circular disks was settled by Danzer [7].
The conjecture was proved in full generality by Tverberg [16] in 1989.
1
Higher dimensional generalizations for families of balls were initiated by Problem
107 [11] of Hadwiger, which states that for any family of thinly distributed balls in En
the property T(n2) implies T. A family of balls is thinly distributed if the distance
between the centers of any two balls is at least twice the sum of their radii. In his
solution, Hadwiger reduced the problem to proving a 3-dimensional lemma (Hilfssatz),
essentially claiming that for two thinly distributed balls inE3 the cone consisting of the
direction vectors of the common transversals of the balls is convex. However, the proof
of this Hilfssatz was not included in the published solution, although at that time it
was available from the editor. A special case, when the two balls are congruent, has
been proved rigorously in [12]. In 1960, Gr?unbaum [10] improved the n2 in Hadwiger?s
statement to 2n?1 using the Topological Helly Theorem and Hadwiger?s Hilfssatz.
Recent progress concerning tranversals of balls has been made by Holmsen, Katchal-
ski and Lewis [12], who proved that there exists a positive integer n0 ? 46 such that
T(n0) implies T for any family of pairwise disjoint unit balls in E3. This bound was
improved by Cheong, Goaoc and Holmsen [5] to 11. On the other hand, a result of
Holmsen and Matou?sek [13] states that there is no such Helly-number if one considers
families of pairwise disjoint translates of an arbitrary convex body in E3.
In the article [1], we generalize the main result of [12]. Our statement also strength-
ens Hadwiger?s theorem [11] for congruent balls. We prove the following theorem.
Theorem 1.1.1. Let n ? 2 and F be a family of unit balls in En with the property that
the mutual distances of the centers are at least 2
p
2+p2 . If F has property T(n2),
then F has a transversal.
2
Our method of proof avoids Hadwiger?s Hilfssatz. The core part is proving that for
a set of unit balls satisfying the above conditions, the direction vectors of the common
transversals of all the balls from a convex set. We manage to prove this by reducing the
problem for the three-dimensional case. Then the convexity allows us to flnish the proof
with the repeated use of Helly?s Theorem and the Spherical Helly Theorem.
Since then, our result has been strengthened by Cheong, Goaoc, Holmsen and Pe-
titjean [6], who proved that for a family of disjoint unit balls in En, T(4n?1) implies
T.
1.2 Problems on iterative processes
History and terminology. There are several results in the literature which deal with
iterative processes in the plane. A typical problem starts with the description of a
geometric construction, which when applied to an initial point set generates additional
points and thus expands it. The problem usually is to prove that repeated expansions
lead to an everywhere dense point set in the plane.
For example K. Bezdek and J. Pach [4] answering a question of L. Fejes T?oth proved
that if one starts with two points (whose distance is ? 2 and difierent from 1 and p3)
then repeated use of the construction \add to the flgure all intersection points of those
unit circles whose centers belong to the existing points set" leads to a dense point set.
Recently D. Ismailescu and R. Radoi?ci?c [14] (and earlier B. Gr?unbaum) showed that the
repeated use of the construction \add to the flgure all the intersection points of lines
which connect pairs of already existing points" also leads to a dense point set (with the
exception of a few particular starting conflgurations). Ismailescu also suggested to study
3
similar problems where one uses the construction \add the circumcenters (incenters resp.)
of all nondegenerate triangles formed by the existing points". It was proved in [15] that
in case of the circumcenters the iterative process always leads to a dense point set of the
plane, and in case of the incenters it always leads to a dense point set in the convex hull
of the initial point set.
Higher dimensional circumcenter problem. In Chapter 2 we present a new ap-
proach to the problem of iterative processes. Instead of analyzing the elementary ge-
ometric properties of the particular iterative processes we prove a key theorem on n-
dimensional closed point sets. Essentially we prove that if a point set inEn is not dense
in its convex hull, then there exists a ball which contains n + 1 a?nely independent
points of the set on the boundary, and all the other points of the set contained in the
ball are close to one of these points. As an application of this theorem we obtain an
a?rmative answer for the higher dimensional version of the circumcenter problem. In
fact we show that more is true, namely the construction \add a point anywhere close to
the circumcenter of each existing simplex" also implies denseness in the whole En.
Planar orthocenter problem. Planar iterative processes can be deflned with respect
of any triangle center. The case of orthocenters (intersection of the three altitudes of
a triangle) was recognized in [15] as a particularly interesting one due to the following
peculiar behavior of the orthocenters: if a point set belongs to a rectangular hyperbola
(a hyperbola for which the asymptotes are perpendicular), then the orthocenters of the
triangles formed by triplets of this point set are also on this hyperbola. We will say
that a noncollinear point set P is orthocentrically closed if for every three noncollinear
points in P, the orthocenter of the triangle determined by these three points is also
4
in P. Observe that the vertices of a triangle together with their orthocenter form an
orthocentrically closed set. These four point sets will be called orthocentric quadruples.
It was conjectured by Iorio, Ismailescu, Radoi?ci?c and Silva in [15] that orthocentrically
closed sets with the exception of orthocentric quadruples are either dense sets in the
plane or are dense subsets of a rectangular hyperbola. We prove in Chapter 3 that it is
also possible that the set is a special inflnite discrete subset of a rectangular hyperbola.
Furthermore, we give an exact characterization of these inflnite discrete subsets.
5
Chapter 2
Higher dimensional circumcenter problem
In this section we give an a?rmative answer for the higher dimensional circumcenter
problem. First we prove the following useful theorem.
Theorem 2.0.1. Let P be a closed set in En which is not dense in its convex hull
and contains n + 1 a?nely independent points. For each 0 < ? < 1 there exists an n-
dimensional ball B which contains n+1 a?nely independent points of P on its boundary
and is essentially empty, meaning that the interior of the concentric ball ?B does not
contain any points from P.
As an application of Theorem 2.0.1 we obtain the answer for the circumcenter prob-
lem as stated in the following theorem.
Theorem 2.0.2. Let P denote a point set in En containing a subset of n + 1 a?nely
independent points, with n ? 1. If there exists a number 0 ? % < 1 such that for any ball
B determined by n+1 a?nely independent points of P the ball %B contains at least one
point from P, then P is dense in En.
Now we introduce some terminology. A ball determined byn+1 a?nely independent
points means the ball of dimension n circumscribed about the simplex determined by
the points. For any ball B with radius r and for any nonnegative number %, the ball %B
denotes the ball concentric to B with radius %r.
6
We will say for sets R;S ?En that R is S-disjoint provided that the interior of R
does not contain any point of S. The convex hull of P will be denoted by convP, and
@(:) stands for the boundary operator.
Proof of Theorem 2.0.1. The basic idea of the proof is the following. First we flnd a
P-disjoint ball in convP. Then we inductively flnd essentially empty balls containing
1;2;:::;n+1 points of P on their boundary. The last ball found by this algorithm will
have the required properties. At flnding the next ball, the concept of transforming one
ball into the other will play the key role:
Suppose that S is a subset of En containing the balls A0 and A1 of dimension n.
We will say that A0 can be transformed to A1 within S if for every t 2 [0;1] there exists
a ball B(t) in S, such that A0 = B(0), A1 = B(1), and both the radii and the position
of the centers of the balls B(t) are changing continuously in t.
We distinguish two cases according to the P-disjointness of the interior of convP.
Case 1. There is a point of P in the interior of the convex hull of P.
First we flnd a P-disjoint ball in the convex hull of P with at least one point of
P n@(convP) on the surface.
Consider the closed inner ?-parallel sets of convP denoted by P?:
P? = fx 2 convP j d(x;@(convP)) ? ?g:
Note that P? is convex. According to the conditions, the interior of convP contains a
P-disjoint ball and also a point of P. Hence there exists a ? > 0 such that the interior
of P? is not P-disjoint while it contains a P-disjoint ball B. This yields that there exists
7
a ball A contained entirely in P? which contains a point of P. Since P? is convex, B
can be transformed into A within P?. The closedness of P yields that there exists a flrst
ball (say B1) along the transformation which contains a point p1 of P on the boundary
while it is still P-disjoint. Since B1 is contained in P?, the point p1 must belong to
P n@(convP), what we wanted.
The ball B1 of radius r will serve as the starting ball in our forthcoming algorithm.
Introduce " = minf(1??)r;(1??)?=2g.
In the following process we will choose a sequence of balls B2;:::;Bn+1 and a
sequence of points p2;:::;pn+1 of P such that for each 2 ? k ? n+1 the following four
conditions hold:
? the radius of Bk is at least as big as the radius of Bk?1
? p1;:::;pk are a?nely independent
? p1;:::;pk belong to the boundary of Bk
? allpointsofP whicharecontainedintheinteriorofBk belongtothe"-neighborhood
of one of the points p1;:::;pk.
Note that the flrst and last conditions guarantee that Bk is essentially empty. Also
notice that the above conditions hold for the ball B1 and the point p1.
We will choose the points and the balls by induction on k. Assume that we already
selected the flrst k members of the sequences satisfying all four of the above conditions.
Let Ak be the k ?1 dimensional a?ne subspace (i. e. a k ?1-dimensional hyperplane)
spanned by p1;:::;pk. Let E be the union of the open "-neighborhoods of p1;:::;pk.
We know that the interior of Bk does not contain points P outside of E. Consider the
8
closed set S = P n E, which is the set of the points of P not contained in the open
"-neighborhood of any of the points p1;:::;pk.
Note that our choice of " provides that S cannot be a subset of Ak. Indeed, that
would mean that all the points ofP are of a distance at most " from Ak, hence the convex
hull of P is contained in the "-neighborhood of Ak. Therefore the distance between p1
(contained in Ak) and convP could be at most ", which contradicts to the assumption
" ? (1??)?=2 < ?.
Deflne C as the maximal a?ne subspace containing the center of Bk and orthogonal
to Ak (hence the linear subspace corresponding to C is the orthogonal complement of the
linear subspace corresponding to A). C is the set of the centers of the spheres passing
through the points p1;:::;pk. Let r be the radius of Bk, and consider among these balls
which, as an additional property, have radius not less than the radius of Bk, and let Cr
denote the set of their centers. Then Cr ? C, and it is easy to see that Cr is obtained
from C by subtracting an open ball. Cr may be considered as the set of all possible
centers of candidates for Bk+1.
Clearly, the dimension of C is n ? k + 1, and therefore the set Cr is path-wise
connected whenever k ? n?1 holds. Moreover, the union of all balls centered in Cr and
containing p1;:::;pk on the boundary cover En nAk.
Since S is not a subset of Ak, there is a non S-disjoint ball A centered in Cr,
containing p1;:::;pk on the boundary. On the other hand, Bk is also centered in Cr,
while it is S-disjoint. The path-connectedness of Cr enables us to transform Bk into A
via balls centered in Cr, and the closedness of S yields that - just as in the beginning of
the proof - there is an S-disjoint ball B along the transformation which contains a point
9
p of S. Since the point p is a?nely independent from the points p1;:::;pk (remember
that it is not contained in Ak), the choices pk+1 = p and Bk+1 = B satisfy the inductive
conditions.
If k = n then Cr consists of two half-lines, which are distinct or their union is the
whole line (this holds when the center of Bn is contained in the hyperplane An). If there
exists a non S-disjoint ball containing p1;:::;pk on its boundary centered in the same
half-line as the center of Bk, then the same process works as in the k ? n ? 1 case.
If this does not hold, then the (n?1)-dimensional hyperplane An separates S and the
center of Bn, yielding that there is no point of P nE in the half-space bounded by An
containing the center of Bn. Hence the intersection of this half-space and the convex
hull of P is contained in the "-neighborhood of the hyperplane An, and therefore the
distance between p1 and the boundary of convP is less then ", a contradiction.
Case 2. There is no point of P in the interior of the convex hull of P.
Choose a point Q in the interior of the convex hull of P and consider the point set
P0 = P[fQg. Applying the process described in the solution of Case 1 for P0 we obtain
an essentially empty ball B satisfying the conditions of the inductive process.
Observe that when selecting the n+1 special a?nely independent points, the flrst
one is Q, and the other points are in P, labeled as p2;:::;pn+1.
Now we drop the point Q, and try to flnd a ball Bn+1 containing n + 1 points of
P on the surface with the desired conditions. Observe that the "-neighborhood of Q is
P-disjoint, and apply the last step of Case 1 with B in place of Bn. The process can fail
only in one case, if the hyperplane A determined by the points p2;:::;pn+1 separates
10
the center of B and the part of P not contained in the "-neighborhoods of the points
p2;:::;pn+1. In the rest of the proof we assume this holds.
First we prove that the radius of the ball circumscribed about p2;:::;pn+1 is greater
than "=(1??). By the choice of ", "=(1??) ? ?=2, therefore it su?ces to show that the
considered radius is at least ?=2. Remember that ? is smaller than the distance between
the additional point Q and the boundary of convP. Hence the ball with center Q and
radius ? is contained in convP. On the other hand, the convex hull is not further from
An than " on one side of An. Comparing these two facts yields that the distance between
Q and An is at least ??", what is greater than ?=2 since " < ?=2. This also yields that
An separates Q and the center of B.
Now an elementary geometric observation yields that since Q is on the surface of
B, and An separates Q from the center of B, the distance between Q and An is strictly
less than the radius of the (n?1)-dimensional ball obtained by taking the intersection of
B and An, what is the same as the radius of the ball circumscribed about p2;:::;pn+1.
Since the distance between Q and An is greater than ?=2, the radius is strictly greater
than ?=2, what we wanted.
Notice that each ball containing p2;:::;pn+1 on the boundary has radius at least
"=(1??). Thus for any such ball G the distance between G and ?G is at least ". Hence
the flrst of the four conditions of the choosing process can be omitted, the last of the four
conditions guarantees essentially emptiness. Therefore in order to flnd the ball Bn+1 we
can search among all balls centered on the line C instead of restricting ourselves to Cr.
11
Since the starting ball is contained in convP, and " is smaller than the radius of
this ball, 2" is strictly smaller than the width of P. This yields that S can not be a
subset of the hyperplane A.
The union of all balls centered on the line C and containing p2;:::;pn+1 coverEnnA,
therefore there exist such a ball which is not S-disjoint. Now the usual transformation
reasoning can be applied, leading to the ball Bn+1.
Now we are able to prove Theorem 2.0.2.
Proof of Theorem 2.0.2. First we will show that set P is dense in its convex hull, the we
prove that the convex hull is the whole space En.
Suppose on the contrary that P is not dense in the convex hull, and apply The-
orem 2.0.1 to the closed point set P with the constant ? = (1 + ?)=2. We obtain an
essentially empty ball B with points p1;p2;:::;pn+1 of P on the boundary. Choose the
points q1;q2;:::;qn of P close enough to the points p1;p2;:::;pn, respectively, such that
for the ball B0 determined by them, %B0 ? ?B holds. It is easy to check that this is valid
if the distance between pi and qi is less than r(1??)=(4+2?) for every i = 1;2;:::;n+1,
where r is the radius of B. By the assumption of Theorem 2.0.2 there is a point of P in
the ball %B0, but this contradicts the essential emptiness of B. Therefore P is dense in
its convex hull.
Now suppose that the convex hull is notEn. Since convP is closed, there is an open
n-dimensional ball in En n convP, and therefore there is a closed ball of this type as
well. The existence of a separating hyperplane between any two disjoint closed convex
sets of En yields that convP must be contained in a closed half-space determined by a
12
hyperplane. Let H denote this half-space, and let G =EnnH. We can also suppose that
the distance between G and convP is 0.
Choose a point Q in G and a ball B centered at Q such that B intersects convP
while the ball ?B is contained in G with the constant ? deflned above. Since the convex
hull is not degenerated, we can also suppose that the intersection B \ convP is not
one point. Choose n + 1 a?nely independent points of convP \ @B and points of P
close enough to them such that for the ball B0 determined by the points chosen from
P, %B0 ? ?B holds as above. Then the existence of a point of P in %B0 yields that the
intersection of P and G is not empty, a contradiction.
Remarks. The assumptions of Theorem 2.0.1 do not imply the existence of a ball
which has at least n+1 a?nely independent points of the given set on its boundary and
whose interior is P-disjoint. To see this, consider the union of a hyperplane and a point
outside of it.
The next example shows that the condition % < 1 in Theorem 2.0.2 cannot be
weakened. Let P be a dense subset of the open ring R = fx 2E2 j 1 < kxk < 2g: Then
P satisfles the condition with ? = 1, but it is not dense in its convex hull.
The following statement is an immediate corollary of Theorem 2.0.1:
Corollary 2.0.1. Let n ? 1, and flx the positive numbers a0;a1;:::;an. Let P be a set
in En containing a subset of n+1 a?nely independent points. If for any n+1 a?nely
independent points p0;p1;:::;pn of P there exists another point p 2 P for which the
ratio-equality p0p : p1p : ??? : pnp = a0 : a1 : ??? : an hold, then P is dense in En.
13
Chapter 3
Planar orthocenter problem
Yielding a complete answer for the orthocenter problem in the plane, we shall prove
the following theorem:
Theorem 3.0.3. If P contains at least three noncollinear points and is an orthocentri-
cally closed set of the plane, then exactly one of the following holds true:
i) P consists of the vertices of a triangle together with its orthocenter.
ii) P is a discrete inflnite subset of a rectangular hyperbola H, parameterizable by
two parameters.
iii) P is a dense subset of a rectangular hyperbola H.
iv) P is a dense point set in the plane.
The proof will be divided into several parts. In Section 3.1 we review geometrical
facts known about rectangular hyperbolas. Section 3.2 describes speciflc subproblems
and show how to flt them together to prove Theorem 3.0.3. The subsequent Sections 3.4-
3.6 will contain detailed solutions of these subproblems.
3.1 Review of elementary properties of hyperbolas
The curve with equation
x2
a2 ?
y2
b2 = 1
is called a hyperbola in standard position. The lines y = (b=a)x and y = ?(b=a)x are its
asymptotes. If b = a, then the asymptotes are perpendicular lines and the hyperbola is
14
called rectangular. If a rectangular hyperbola is rotated by ?=4, the asymptotes become
the x- and y-axis, and it turns out that the new equation of the hyperbola is xy = fi,
where fi is a constant. A very straight and simple computation using coordinates shows
the following two properties:
Hyperbola Property 3.1.1. If a rectangular hyperbola passes through the vertices of
a given triangle, then it also passes through the orthocenter of that triangle.
Hyperbola Property 3.1.2. If one extends any chord (connecting to points of the same
branch) of a rectangular hyperbola at both ends until the line of extension intersects the
coordinate axis, then these two segments are of equal length.
Equivalently to the last property we have the following:
Hyperbola Property 3.1.3. Assume a point P and a rectangular coordinate system is
given. One can construct point-by-point the unique rectangular hyperbola (in this coor-
dinate system) passing through point P in the following way: Take any line ? containing
P and label by X and Y its intersection points with the x and y-axes, respectively. Then
the re ection of point P around the midpoint of segment XY gives a point P0 on the
hyperbola.
A theorem called Feuerbach?s Conic Theorem (proved by Brianchon and Poncelet
in [3] in 1821, see e. g. Problem 46 in [8]) says that
Hyperbola Property 3.1.4. (Feuerbach Conic Theorem) The locus of the centers
of those rectangular hyperbolas which pass through three given noncollinear points (and
thus, according to Hyperbola Property 3.1.1, also pass through the orthocenter of this
triangle) is the so called nine point circle (i.e. the circle which contains the midpoints
15
of the sides, the points half way from the orthocenter to the vertices, and the feet of the
altitudes).
As an immediate consequence of the Feuerbach Conic Theorem we have:
Hyperbola Property 3.1.5. If four points P;Q;R and S are given such that no three
of them are collinear and point S is difierent from the orthocenter of the triangle PQR,
then there is a unique rectangular hyperbola passing through them.
Indeed, consider the Feuerbach circles of the triangles PQR and PQS. Since S is not
the orthocenter of the triangle PQR, the two Feuerbach circles are difierent and thus they
either intersect each other in two points or they are tangent to each other. The midpoint
Y of PQ is a common point of the Feuerbach circles. Let X be the other common
point (in case of tangency let X = Y). X and Y are the only candidates for the center
of a perpendicular hyperbola containing the given four points. There is an important
difierence between X and Y: In case of X the axis of the two rectangular hyperbolas
containing the triplets P;Q;R and P;Q;S coincide and thus the two hyperbolas are
identical. This does not hold for Y, unless X = Y.
3.2 Outline of the proof of Theorem 3.0.3
According to the Introduction a set P is orthocentrically closed if it contains the
orthocenters of every three noncollinear points of P. It was also mentioned that the
vertices of a triangle together with their orthocenter form an orthocentrically closed set.
Case i) in Theorem 3.0.3 is the case of orthocentric quadruples.
Let P be an orthocentrically closed point set and assume P contains four points,
such that no three of them is collinear and the four points do not form an orthocentric
16
quadruple. It is known (see Hyperbola Property 3.1.5) that there exist a rectangular
hyperbola H passing through these four points. According to Hyperbola Property 3.1.1
the intersection P \ H is also an orthocentrically closed point set. Moreover, it was
proved in [15] that P is unbounded. Any subset of a hyperbola is either a discrete point
set or it has at least one limit point. We will show in Section 3.3 that the existence of
one single limit point of P \H implies that P \H is a dense subset of the hyperbola H,
i.e. it is of type iii) in Theorem 3.0.3. The case when P is an inflnite discrete point set
is listed as case ii) in Theorem 3.0.3. We will address the existence of sets of type ii) in
Sections 3.4 and 3.5 by giving both the geometric and the algebraic characterizations.
We will show in Section 3.6 that the existence of one additional point of P outside
the rectangular hyperbola H (which already contains inflnite many points of P) implies
that P is a dense point set of the plane. Thus we have that iv) is the only additional
possibility besides i), ii) and iii) in Theorem 3.0.3.
3.3 If P has a convergent subsequence on the hyperbola H, then P is a dense
set of H.
Again let H be a rectangular hyperbola with equation xy = fi. Assume on the
contrary that the existence of a convergent subsequence of P on the hyperbola H does
not imply that P is a dense set of H. Without loss of generality we may assume that
there is a convergent sequence of points Pi 2 P(i = 1;:::), whose x-coordinates form
a positive, increasing, convergent sequence. Let P be the limit point of this sequence
(Figure 3.1). Furthermore, assume that there is a point Q on the same branch of H such
17
that the open hyperbola arc (PQ) does not contain points from P (note that P and Q
do not necessarily belong to P).
Starting with P1, for a su?ciently small ? > 0 we are going to choose subsequently
four points P1;Pi;Pj and Pk from the above sequence so that each succeeding point is
signiflcantly closer (say ? times closer) to P than the previous one.
Let O be the orthocenter of the triangle P1PjPk. Notice that O belongs to the
other branch of hyperbola H. Finally consider the orthocenter O? of the triangle P1PiO.
Obviously O? is a point on the flrst branch of H again. Moreover, if ? is su?ciently
small, then both Pj and O? are arbitrarily close to P, while they are separated by P,
therefore O? belongs to the open hyperbola arc (PQ), a contradiction.
kj
i P
P
P
P
1
O
O*QP
Figure 3.1: The case of a convergent sequence
18
3.4 Geometriccharacterizationofinflnite, discreteandorthocentricallyclosed
sets of a rectangular hyperbola
In this section, we characterize all inflnite and discrete orthocentrically closed sub-
sets of a rectangular hyperbola. It turns out that discreteness implies a symmetrical
structure for the diagonals (segments connecting pairs of points of the point set) which
best can be compared to the diagonal structure of the even-sided regular polygons: for
each diagonal there are both parallel and perpendicular sets of diagonals covering all
vertices of the polygon (except at most two vertices). In order to give the precise char-
acterization we need the following notations.
We will refer to the branches of the given rectangular hyperbola H as positive and
negative branches (denoted by H+ and H?) according to the signs of the x-coordinates
of their points.
Assume that set P is a discrete, inflnite, orthocentrically closed subset of a rectan-
gular hyperbola H. Denote by P+ (and P?) the set of those points of P which belong
to the positive branch (negative branch respectively) of H. It was proved in [15] that P
is an unbounded set. In fact, it is easy to prove, that both P+ and P? are unbounded
sets, moreover, they are unbounded sets along both direction of the hyperbola branches.
Let us label the points of the set P+ using all integers in the order which matches the
order of the x-coordinates of the points.
Let i;j and k be three difierent points of P+. We already know that the intersection
point of the negative branch P? with the line perpendicular to ij through k belongs to
the set P, since it is the orthocenter of the triangle ijk. It is not automatic that similar
19
perpendicular projections of the points i and j also give points of P?. Before we state
this property together with some additional ones we introduce the following notations:
We deflne the P-length of a diagonal ij in P+ (or in P?) by the number of points
of set P+ (of set P? respectively) contained by the open hyperbola arc (ij).
Let Oijk (where i;j;k are difierent points of P) be the orthocenter of the triangle
ijk.
Denote by ?ij (where i;j 2 P+ ) the projection from the branch P+ to the branch
P? along the direction which is perpendicular to the line ij.
Denote by \Shift" the map within the set P? (or P+ ), where each point of P?
(of P+) is mapped to its neighbor along the same direction of the hyperbola branch H?
(H+ resp.).
We will prove the following characterization:
Theorem 3.4.1. An inflnite discrete point set P of the rectangular hyperbola H is
orthocentrically closed if and only if it satisfles the following three conditions:
1. For each i;j 2 P+ the projection ?ij gives a one-to-one correspondence between
the points of P+ and P?.
2. For each diagonal d in P+ it is true that each point of P+ is the endpoint of a
diagonal parallel to d (this condition includes tangent lines as degenerate diagonals).
3. For each diagonal in P? there is a parallel diagonal in P+.
Proof of Theorem 3.4.1. Since this theorem is an \if and only if" theorem, we need to
show that the listed conditions are both necessary and su?cient conditions. We start
addressing the \necessary" part by proving a chain of elementary facts:
20
1. First we prove Condition 1 for diagonals of P-length equal to two: Without loss of
generality consider the diagonal 14 of P+, which has length three. The only nontrivial
part of Condition 1 is to show that the lines perpendicular to the diagonal 14 through its
endpoints intersect H? at points of P. Consider the perpendicular line through endpoint
1, and assume indirectly that the intersection point F is not a point of P?. We indicate
this on Figure 3.2.a by an \empty circle" as a point F. Denote the orthocenter O123 by
E, which is a point of P? difierent from F. We distinguish two cases:
Case 1: The x-coordinate of E is greater than that of F. Consider the triangle E14
and its orthocenter (Figure 3.2.a). The ray connecting E to the orthocenter must lie
between rays ?!E2 and ?!E1. This means that the orthocenter of triangle E14 is contained
by the open hyperbola arc (12), a contradiction.
E
a)
3 42
1
F FE
1
G
2 3 4
b)
Figure 3.2: The set is closed under the projection ?ij
Case 2: The x-coordinate of E is smaller than that of F. Denote the orthocenter
of the triangle E14 by G (Figure 3.2.b). G is a point of H+. The x-coordinate of G
21
must be less than that of point 1. Consider the triangle EG2 and its orthocenter. The
ray connecting E to this orthocenter must be between rays ?!E4 and ?!E2. This means
that the orthocenter of the triangle EG2 is point 3, but then there are two difierent
perpendiculars to this line through point 2, a contradiction.
2. WeproveCondition1fordiagonalsofP-lengthequaltoone: Withoutlossofgenerality
consider the diagonal 13 of P+, which has length one. The only nontrivial part of
Condition 1 is to show, that the lines perpendicular to diagonal 13 through the endpoints
intersect H? at points of P?. It is enough to show this for one of the endpoints, say
for endpoint 3. We already know that the images of points 1;2;3 and 4 under the
perpendicular projection ?14 belong to P? and they are consecutive points in that set.
Denote them by A;B;C and D (Figure 3.3.a). We also know that A is the orthocenter
of the triangle 123, thus ?12(3) = A. Since points 3 and 4 are consecutive points in P
we have that ?12(4) = B. The orthocenter of the triangle 134 must be between B and
D on H?, thus it is equal to C. This leaves only one option for the orthocenter of the
triangle 13B and that is point 3, which we wanted to prove.
3. We prove Condition 1 for diagonals of P-length zero: Without loss of generality
consider the diagonal 23 of P+, which has length zero. It is enough to show that the
diagonals 23 and 14 are parallel.
Denote, again, by A the image of point 1 under the perpendicular projection ?14.
From the paragraph labeled as 1. above we already know that the perpendicular pro-
jection ?13 maps point 2 to point A, i.e. A is the orthocenter of the triangle 123, thus
23 is perpendicular to A1. Since A1 is perpendicular to 14, we get that 23 and 14 are
parallel.
22
A B
CD
1
2
3 4
a)
E
J
F
i
i+1
j
b)
j?1
Figure 3.3: Inductive steps
4. We prove Condition 1 and 2 for diagonals of P-length 5;6;::: : We are going to
use induction on the length of the diagonals of P+. Assume that we already proved
Condition 1 and 2 for all diagonals of P-length less than N. Consider a diagonal ij of
length N, i.e. j = i+N +1 (see Figure 3.3.b). All we need to prove is that diagonal ij
is parallel to diagonal (i + 1)(j ?1). On the contrary assume that these two diagonals
intersect each other, say at F, so that i separates F and j. According to Condition 1
there is a point J 2 P? so that the ?ij(j) = J. Denote ?ij(j ? 1) 2 P? by E. Since
j?1 and j are consecutive points of P? both triangles i(j?1)j and (i+1)(j?1)j must
have their orthocenter adjacent to J, therefore at E. Thus both diagonals i(j ?1) and
(i+1)(j ?1) are perpendicular to the line jJ, a contradiction.
5. We prove Condition 3: Consider a diagonal ij of P+. According to Condition 1 there
are points, say I and J 2 P? so that the ?ij(i) = I and ?ij(j) = J 2 P?. Project the
point j onto P? perpendicularly to each of the diagonals ij;i(j ? 1);i(j ? 2);:::(i;i).
23
The flrst image, as we know, is J, and the last image is I. Notice that the images at the
projections are difierent and the number of diagonals we consider equals the number of
points on the hyperbola arc IJ. Thus we have that \moving one endpoint of the diagonal
ij to its neighbor implies that the perpendicular projection of that endpoint moves to its
neighbor on the other hyperbola branch". This means that if we start by two diagonals
belonging to difierent hyperbola branches, then we can change gradually one of them
(by moving one of its endpoint to a neighboring point) until the perpendicular direction
of the changed diagonal coincides with the perpendicular direction of the unchanged
diagonal.
6. We prove that Conditions 1;2 and 3 are su?cient in Theorem 3.4.1: We need to verify
that such sets are orthocentrically closed. Take three points from P. If they belong to
the same branch of the hyperbola then Condition 1 implies that the orthocenter of this
triangle belongs to P. Without loss of generality assume that two of the vertices, say i
and j belong to H+ and the third one, say O, belongs to H?. According to Condition 3,
P? has a diagonal, say d, which is parallel to ij. According to Condition 1, the projection
of O onto H+ in the direction perpendicular to the diagonal d, belongs to P+, which we
wanted to show.
3.5 Existence and algebraic characterization of the inflnite, discrete and
orthocentrically closed sets of the rectangular hyperbola
Let H be the rectangular hyperbola deflned by the equation xy = fi. The points of
H can be identifled with their x-coordinates, and this gives an isomorphism between H
24
and the x-axis except the origin. Throughout the section h(x) will denote the point of
H with the given abscissa x. In other notations we follow Section 3.4.
We will show that there exists a discrete subset ofH which is orthocentrically closed.
So far we have proved a geometric necessary and su?cient condition for such a point
set detailed in Theorem 3.4.1; easy algebraic arguments will yield that there really exist
such a point set. In fact we give an algebraic characterization for these sets, also yielding
that there are inflnitely many of them on the same rectangular hyperbola.
Suppose that P is a discrete subset of H with the given property. Let h(x0) be an
arbitrary point of P+. Let the points of P+ be fh(xi)g1i=?1, labeled in accordance with
the ordering of the abscissas, so 0 < xj < xk holds for any integers j < k.
Condition 2 of Theorem 3.4.1 yield the following parallelism property:
h(xj) h(xk) k h(xj?d) h(xk+d)
for any integers j, k and d with j < k.
Using the equation of the hyperbola this condition turns into the following algebraic
equality:
xj xk = xj?d xk+d (3.1)
With the help of (3.1) we can express all xi?s in terms of x0 and x1. Introducing
the notations a := x0 and b := x1 will simplify the formulae.
We shall prove by induction onjijthat the following formula holds for every integeri.
xi = bi a1?i (3.2)
25
Clearly (3.2) is true for i = 0;1. First we show it for i = ?1. Applying (3.1) for
j = 0, k = 1 and d = 1 yields that x2 = ab=x?1. On the other hand, the choice j = ?1,
k = 0 and d = 1 gives x?2 = x?1a=b. Now in the case j = ?1, k = 1 and d = 1 we
obtain the equality x?1 = a2=b, and this was our goal.
Suppose now that (3.2) is proved for all i with jij < n. Applying (3.1) for j = 0,
k = 1 and d = n?1 we obtain
xn = ab=(b1?n an) = bn a1?n:
Furthermore, the choice j = ?1, k = 0 and d = n?1 yields
x?n = b?1 a3=(bn?1 a2?n) = b?n a1+n;
flnishing the proof of (3.2).
So far we have described the points of P+. Now turn to the points with negative
abscissa. We have proved in Condition 1: of Theorem 3.4.1 that those can be obtained
by taking the orthogonal projection of P+ onto H? with respect to an arbitrarily chosen
diagonal of P+.
Let choose the diagonal to be h(a)h(b). For any xi let h(x0i+1) denote the projection
of xi onto H?. The following holds:
x0i+1 = ?fi2=(xi ab) = ?fi2 b?i?1 ai?2 = ?fi2 b?(i+1) a?3+(i+1):
Therefore the negative part of P consists of all the points with x-coordinates of the
form
26
x0i = fi2(?bi a?3?i); (3.3)
where i is any integer.
According to Theorem 3.4.1 for the su?ciency we have to guarantee that for any
given diagonal of P?, there exists a diagonal in P+ parallel to the given one. Translating
to algebra we get the following statement: for any difierent integers i and j there exist
integers k 6= l such that
fi4bi+ja?6?(i+j) = bk+la2?(k+l);
or, equivalently,
9s 2Z: (b=a)s = (a=pfi)8: (3.4)
Since all the algebraic transformations done so far are reversible, we have proved
the following theorem:
Theorem 3.5.1. An inflnite discrete subset of the rectangular hyperbola H is orthocen-
trically closed if and only if it is described by the forms (3.2) and (3.3) where a < b are
positive real numbers satisfying the condition (3.4).
We note that for the choice a = pfi condition (3.4) holds for any positive number b
with s = 0. In this case the point set P is symmetric to the line x = y. Also notice that
for any given real number a > 1 and integer s, the equation (3.4) has a solution for b;
in other words, for any flxed point of the hyperbola there are inflnitely many difierent,
discrete, orthocentrically closed subsets containing that point.
27
3.6 If P is not on the hyperbola, then it is a dense set of the plane.
We shall now show that if an orthocentrically closed point set is not contained in a
rectangular hyperbola, then it must be dense in the whole plane. We are going to use
the notations of Section 3.4. We will also label the points of P? by the accented integers
(n0) with the order which matches the order of the x-coordinates.
We can assume that the point set P is closed. Indeed, if a planar point set is ortho-
centrically closed, then the same property holds for its closure: taking any nondegenerate
triplet of the closure, and point sequences converging to the vertices, the orthocenters
of the triplets of the sequences will converge to the orthocenter of the given triangle.
This yields that we should prove that a closed and orthocentrically closed set is either a
subset of a rectangular hyperbola or equals to the whole plane itself.
Our argument is divided into two steps: the flrst step is to show that if the closed set
P contains an inflnite orthocentrically closed discrete subset of a rectangular hyperbola,
and also a point outside of the hyperbola, then it contains the whole hyperbola. The
second step is to prove that if the closed set P contains an entire rectangular hyperbola
and one additional point, then it is the whole plane.
Lemma 3.6.1. Suppose the P is an inflnite discrete orthocentrically closed point of
the rectangular hyperbola H. Then for any point P outside of H, the set P [ fPg is
generating a dense subset of H by the orthocenter transformation.
Proof. As an extension of our former deflnition, let ?ij(P) denote the intersection points
of the hyperbola H and the line perpendicular to ij through P. First we show that
there exists a diagonal ij of P+ such that the two points of ?ij(P) do not belong to P.
Indeed, choose the diagonals n(2n) and let n tend to inflnity. Then the direction vectors
28
of the diagonals are tending to the horizontal direction, and therefore unless the given
point P is on the y-axis, the projections have a limit point on the hyperbola. Since the
set P is discrete, there must be a diagonal of the chosen ones for which the projection
does not belong to P. We can use the same argument for the diagonals (?n)(?2n)
yielding the same result for any point P outside of the x-axis. Therefore the statement
holds for any point except for the origin. Finally, if P is the origin, and ?ij(P) belongs
to P then it is easy to see that ?i(j+1)(P) does not belong to P: Theorem 3.4.1 yields
that the projections of P+ are shifted by one when taking ?i(j+1) instead of ?ij, and
therefore two projection lines cannot intersect in the region between the two branches of
the hyperbola.
We can also assume that the diagonal ij has the property that the projection of P
onto the diagonal is a point of H between i and j. Moreover, we can choose a diagonal
k0l0 of P? parallel to ij and satisfying the same condition. Finally, let e denote the line
perpendicular to ij and passing through P (see Figure 3.4.a).
We will deflne an inflnite point set on e by taking the orthocenters of certain triplets,
and we shall show that the intersections of e and the hyperbola H belong to the closure
of our inflnite point set, yielding a contradiction.
Let Dp and Dn denote the Thales discs of the segments ij and k0l0, respectively.
We claim that Dp \Dn is empty. Indeed, if we take points Q and R as the intersection
points of the diagonal ij with the y-axis and the x-axis, then the segment ij is strictly
contained in the segment QR. We obtain the segment ST in the same manner from k0l0.
Now, the Thales discs Dp and Dn are strictly contained in the Thales discs of QR and
29
ST, while an easy geometric observation yields that those are touching each other at the
origin, hence the intersection of Dp and Dn must be empty.
Orient e such that the points of e\Dn are \below" the points of e\Dp. We note
that if we take a point M of e outside of Dp, then OijM (the orthocenter of the triangle
ijM) is in the intersection of e and Dp. Moreover, if we take two points M1 and M2
from the same component of enDp such that M1 < M2, then OijM1 > OijM2 holds as
well. The same observations hold for Dn in place of Dp.
Let P0 = P and deflne the sequence fPng1n=0 ? e in the following way: if Pn is not
in Dp then let Pn+1 = OPnij, otherwise let Pn+1 = OPnk0l0. It is easy to see that for
n ? 2 the point Pn is on the open segment bounded by the intersection points of e with
ij and k0l0. Without loss of generality suppose that P2 is outside of Dp, therefore P3 is
in Dp, and it is easy to see that P2n is in Dn while P2n+1 is in Dp for any n ? 2.
If P2 ? P4 holds, then by induction on n we obtain easily that P2n?1 ? P2n+1
and P2n ? P2n+2 holds true for any n ? 2, while if P2 ? P4, then P2n?1 ? P2n+1 and
P2n ? P2n+2 for any n ? 2. This means that the subsequences fP2n+1g1n=1 and fP2ng1n=1
are monotonic and bounded, therefore their limits exist. Let L1 and L2 denote the limit
points, respectively. Then L1 2 Dp and L2 2 Dn.
Note that the following property holds for the limit points: L2 is the orthocenter of
the triangle k0l0L1 and L1 is the orthocenter of the triangle ijL2. We claim that L1 and
L2 must be the intersection points of the hyperbola with the line e.
We refer to Hyperbola Property 3.1.5. Since the points i, j, k0 and l0 do not form
an orthocentric system (remember that ijkk0l0), it su?ces to show that there is a rect-
angular hyperbola containing all the six points i, j, k0, l0, L1 and L2. Take a rectangular
30
hyperbola through i, j, L2 and k0. Then this hyperbola also contains L1, since this is the
orthocenter of the triangle ijL2. Moreover, l0 is also on the hyperbola, being the ortho-
center of the triangle k0L1L2. Therefore such a hyperbola exists, and by uniqueness it is
H. Hence the intersection points of e and H belong to the closure of the orthocentrically
generated point set, contradicting the choice of the diagonal ij.
D
n
p
P1
D
M
P
P?
N
T
P2
L
L
1
2
j
ei
k?
l?
P
a) b)
Figure 3.4: A point outside the hyperbola is generating a dense set
The flnal step in the proof of Theorem 3.0.3 is to show that
Lemma 3.6.2. Suppose that H is a rectangular hyperbola. For any point P outside of H,
the set H[fPg is generating an everywhere dense subset of the plane by the orthocenter
transformation.
Proof. Let us choose a line ? through P intersecting H+ in the point M. Moreover,
assume that the angle between ? and the tangent of H at M is not ?=2. Let m denote
the slope of a line perpendicular to ?. Consider a tangent with slope m of the positive
branch of H, and let T be the common point of this tangent line and the hyperbola. Let
31
N denote the second intersection point of the positive branch of H and the line through
M with slope m (see Figure 3.4.b).
Consider the family of triangles with common vertex P and with two other vertices
on H+ so that their connecting segment has slope m. The orthocenters of these triangles
are on line ?. If the vertices difierent from P converge to point T, then the orthocenters
of these triangles converge to point P0 of line ? for which \P0TP = ?=2. On the other
hand, if we choose the two variable vertices of the triangle as M and N, then the resulted
orthocenter is M. If we change continuously the two vertices of the triangle between
these limits, the orthocenters are changing continuously between M and P0. Therefore
the whole segment MP0 belongs to the closure of the set of the orthocentrically generated
points.
The same argument with P0 in the place of P yields that the segment PM is also
generated. Now let the point Q run along the segment PP0, what we already know
to be orthocentrically generated. It is easy to see that the points Q0 2 ? for which
\QTQ0 = ?=2 cover the whole line ?, hence ? is orthocentrically generated.
The same argument works if we replace the positive branch of the hyperbola with
the negative branch. Moreover it is easy to check that except for the line y = x no line
can be perpendicular to both branches of the hyperbola (where the angle between and
the line are understood to the angle between the line and the tangent to the hyperbola
at the intersection point). Therefore all the lines with positive slope passing through
P, except (optionally) for the line y = x, are generated. The union of these lines is
the union of two inflnite domains bounded by the horizontal and vertical lines through
P, what we call a wedge with vertex P. Now replace P by any point Q in the wedge
32
with vertex P, the same arguments yield that the wedge with vertex Q is also generated.
Since the union of all of these wedges cover the plane, we obtain that the orthocentrically
generated points form a dense subset of the plane.
33
Bibliography
[1] G. Ambrus, A. Bezdek and F. Fodor, A Helly-type transversal theorem for n-
dimensional unit balls, to appear in Archiv der Math.
[2] G. Ambrus, A. Bezdek, On iterative processes generating dense point sets, to appear
in Period. Math. Hung.
[3] C.-J. Brianchon and J.-V. Poncelet, Recherches sur la d?etermination d?une hyper-
bole ?equilat?ere, au moyen de quatre conditions donn?ees, , Ann. des Math. 1 (1821),
no.4, 205-220.
[4] K. Bezdek and J. Pach, A point set everywhere dense in the plane, Elem. Math. 40
(1985), no.4, 81-84.
[5] O. Cheong, X. Goaoc, A. Holmsen, Helly type theorems for line transversals to unit
balls in R3, (2004).
[6] O. Cheong, X. Goaoc, A. Holmsen and S. Petitjean, Helly-type theorems for line
transversals to disjoint unit balls, to appear.
[7] L. Danzer, ?Uber ein Problem aus der kombinatorischen Geometrie. Arch. Math. 8
(1957), 347{351.
[8] H. D?orrie, 100 Great Problems of Elementary Mathematics: The History and Solu-
tions, New York: Dower,1965.
[9] B. Gr?unbaum, On common transversals, Arch. Math. 9 (1958), 465{469.
[10] B. Gr?unbaum, Common transversals for families of sets, J. Lond. Math.Soc. 35
(1960), 408{416.
[11] H. Hadwiger, Problem 107, Nieuw Arch. Wiskunde (3) 4 (1956), 57; Solution,
Wiskundige Opgaven 20 (1957), 27{29.
[12] A. Holmsen, M. Katchalski, and T. Lewis, A Helly-type theorem for line transversals
to disjoint unit balls, Discrete Comput. Geom. 29 (2003), no. 4, 595{602.
[13] A. Holmsen, and J. Matou?sek, No Helly theorem for stabbing translates by lines in
R3, Discrete Comput. Geom. 31 (2004), no. 3, 405{410.
[14] D. Ismailescu and R. Radoi?ci?c, A dense planar point set from iterated line intersec-
tions, Computational Geometry, 27 (2004), 257-267.
34
[15] M. Iorio, D. Ismailescu, R. Radoi?ci?c and M. Silva, On point sets containing their
triangle centers, to appear.
[16] H.Tverberg, Proof of Gr?unbaum?s conjecture on common transversalsfor translates,
Discrete Comput. Geom. 4 (1989), 191{203.
35