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:




Library Locked Library locked




Author, Editor

Author(s):

Alvarez, Victor
Bringmann, Karl
Curticapean, Radu
Ray, Saurabh

dblp
dblp
dblp
dblp

Not MPG Author(s):

Alvarez, Victor
Curticapean, Radu

Editor(s):

Dey, Tamal K.
Whitesides, Sue

dblp
dblp

Not MPII Editor(s):

Dey, Tamal K.
Whitesides, Sue

BibTeX cite key*:

AlvarezBCS12

Title, Booktitle

Title*:

Counting Crossing Free Structures

Booktitle*:

Proceedings of the Twenty-Eight Annual Symposium on Computational Geometry (SCG'12)

Event, URLs

URL of the conference:

http://socg2012.web.unc.edu/

URL for downloading the paper:

http://doi.acm.org/10.1145/2261250.2261259

Event Address*:

Chapel Hill, NC, USA

Language:

English

Event Date*
(no longer used):


Organization:

ACM

Event Start Date:

17 June 2012

Event End Date:

20 June 2012

Publisher

Name*:

ACM

URL:

http://www.acm.org/

Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

61-68

Year*:

2012

VG Wort Pages:


ISBN/ISSN:

978-1-4503-1299-8

Sequence Number:


DOI:

10.1145/2261250.2261259



Note, Abstract, ©


(LaTeX) Abstract:

Let P be a set of n points in the plane. A crossing-free structure on P is a straight-edge planar graph with vertex set in P. Examples of crossing-free structures include triangulations of P, and spanning cycles of P, also known as polygonalizations of P, among others. There has been a large amount of research trying to bound the number of such structures. In particular, bounding the number of triangulations spanned by P has received considerable attention. It is currently known that every set of n points has at most O(30^n) and at least Ω(2.43^n) triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set P. For example, no algorithm for counting triangulations is known that, on all instances, performs faster than enumerating all triangulations. In this paper we develop a general technique for computing the number of crossing-free structures of an input set P. We apply the technique to obtain algorithms for computing the number of triangulations and spanning cycles of P. The running time of our algorithms is upper bounded by n^O(k), where k is the number of onion layers of P. In particular, we show that our algorithm for counting triangulations is not slower than O(3.1414^n). Given that there are several well-studied configurations of points with at least Ω(3.464^n) triangulations, and some even with Ω(8^n) triangulations, our algorithm is the first to asymptotically outperform any enumeration algorithm for such instances. In fact, it is widely believed that any set of n points must have at least Ω(3.464^n) triangulations. If this is true, then our algorithm is strictly sub-linear in the number of triangulations counted. We also show that our techniques are general enough to solve the restricted triangulation counting problem, which we prove to be W[2]-hard in the parameter k. This implies a “no free lunch” result: In order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of structures.



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{AlvarezBCS12,
AUTHOR = {Alvarez, Victor and Bringmann, Karl and Curticapean, Radu and Ray, Saurabh},
EDITOR = {Dey, Tamal K. and Whitesides, Sue},
TITLE = {Counting Crossing Free Structures},
BOOKTITLE = {Proceedings of the Twenty-Eight Annual Symposium on Computational Geometry (SCG'12)},
PUBLISHER = {ACM},
YEAR = {2012},
ORGANIZATION = {ACM},
PAGES = {61--68},
ADDRESS = {Chapel Hill, NC, USA},
ISBN = {978-1-4503-1299-8},
DOI = {10.1145/2261250.2261259},
}


Entry last modified by Anja Becker, 01/25/2013
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)
[Library]
Created
12/13/2012 10:25:02 AM
Revision
1.
0.


Editor
Anja Becker
Karl Bringmann


Edit Date
25.01.2013 11:14:41
13.12.2012 10:25:02