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:








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 PR2, 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 PP. 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 P0 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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for 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