Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2019) |
last year
(2018) |
two years ago
(2017) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Klein, Rolf
Kutz, Martin
dblp
dblp
Not MPG Author(s):
Klein, Rolf
Editor(s):
BibTeX cite key*:
KlKu2006b
Title, Booktitle
Title*:
The Density of Iterated Crossing Points and a Gap Result for Triangulations of Finite Point Sets
Booktitle*:
Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06
Event, URLs
URL of the conference:
http://socg06.cs.arizona.edu/
URL for downloading the paper:
http://delivery.acm.org/10.1145/1140000/1137897/p264-klein.pdf?key1=1137897&key2=8341432811&coll=GUIDE&dl=GUIDE&CFID=26118200&CFTOKEN=95525732
Event Address*:
Sedona, Arizona, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
5 June 2006
Event End Date:
7 June 2006
Publisher
Name*:
ACM
URL:
http://www.acm.org/
Address*:
New York, NY, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
264-272
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
1-59593-340-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Consider a plane graph
G
, drawn with straight lines. For every pair
a,b
of vertices of
G
, we compare the shortest-path distance between
a
and
b
in
G
(with Euclidean edge lengths) to their actual distance in the plane. The worst-case ratio of these two values, for all pairs of points, is called the
dilation
of
G
. All finite plane graphs of dilation 1 have been classified. They are closely related to the following iterative procedure. For a given point set
P
⊆
R
^{2}
, we connect every pair of points in
P
by a line segment and then add to
P
all those points where two such line segments cross. Repeating this process infinitely often, yields a limit point set
P
^{∞}
⊇
P
. This limit set
P
^{∞}
is finite if and only if
P
is contained in the vertex set of a triangulation of dilation 1.The main result of this paper is the following gap theorem: For any finite point set
P
in the plane for which
P
^{∞}
is infinite, there exists a threshold λ > 1 such that
P
is not contained in the vertex set of any finite plane graph of dilation at most λ. As a first ingredient to our proof, we show that such an infinite
P
^{∞}
must lie dense in a certain region of the plane. In the second, more difficult part, we then construct a concrete point set
P
_{0}
such that any planar graph that contains this set amongst its vertices must have a dilation larger than 1.0000047.
URL for the Abstract:
http://doi.acm.org/10.1145/1137856.1137897
Download
Access Level:
Internal
Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort
BibTeX Entry:
@INPROCEEDINGS
{
KlKu2006b
,
AUTHOR = {Klein, Rolf and Kutz, Martin},
TITLE = {The Density of Iterated Crossing Points and a Gap Result for Triangulations of Finite Point Sets},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06},
PUBLISHER = {ACM},
YEAR = {2006},
PAGES = {264--272},
ADDRESS = {Sedona, Arizona, USA},
ISBN = {1-59593-340-9},
}
Entry last modified by Uwe Brahm, 02/28/2008
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
Pascal Schweitzer
Created
02/28/2007 01:51:59 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
2007-07-18 14:44:27
07/07/2007 00:44:02
21.06.2007 17:18:45
20.06.2007 14:34:52
20.06.2007 14:26:38