Quadrangulations of planar sets

Godfried Toussaint

doi:10.1007/3-540-60220-8_64

Quadrangulations of planar sets

Godfried Toussaint

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if 5 is a polygon, or the interior of the convex hull of S, if 5 is a set of points, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or sets of points admit quadrangulations, even when the quadrangles are not required to be convex (convex quadrangulations). In this paper we briefly survey some recent results concerning the characterization of those planar sets that always admit quadrangulations (convex and non-convex) as well as some related computational problems.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings
Editors	Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	218-227
Number of pages	10
ISBN (Print)	3540602208, 9783540602200
DOIs	https://doi.org/10.1007/3-540-60220-8_64
State	Published - 1995
Event	4th Workshop on Algorithms and Data Structures, WADS 1995 - Kingston, Canada Duration: Aug 16 1995 → Aug 18 1995

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	955
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th Workshop on Algorithms and Data Structures, WADS 1995
Country/Territory	Canada
City	Kingston
Period	8/16/95 → 8/18/95

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-60220-8_64

Cite this

Toussaint, G. (1995). Quadrangulations of planar sets. In S. G. Akl, F. Dehne, J.-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings (pp. 218-227). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 955). Springer Verlag. https://doi.org/10.1007/3-540-60220-8_64

Quadrangulations of planar sets. / Toussaint, Godfried.
Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. ed. / Selim G. Akl; Frank Dehne; Jörg-Rüdiger Sack; Nicola Santoro. Springer Verlag, 1995. p. 218-227 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 955).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Toussaint, G 1995, Quadrangulations of planar sets. in SG Akl, F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 955, Springer Verlag, pp. 218-227, 4th Workshop on Algorithms and Data Structures, WADS 1995, Kingston, Canada, 8/16/95. https://doi.org/10.1007/3-540-60220-8_64

Toussaint G. Quadrangulations of planar sets. In Akl SG, Dehne F, Sack JR, Santoro N, editors, Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. Springer Verlag. 1995. p. 218-227. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-60220-8_64

Toussaint, Godfried. / Quadrangulations of planar sets. Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. editor / Selim G. Akl ; Frank Dehne ; Jörg-Rüdiger Sack ; Nicola Santoro. Springer Verlag, 1995. pp. 218-227 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d9d51e7eb53646cabb0f5bdd05ae74cf,

title = "Quadrangulations of planar sets",

abstract = "Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if 5 is a polygon, or the interior of the convex hull of S, if 5 is a set of points, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or sets of points admit quadrangulations, even when the quadrangles are not required to be convex (convex quadrangulations). In this paper we briefly survey some recent results concerning the characterization of those planar sets that always admit quadrangulations (convex and non-convex) as well as some related computational problems.",

author = "Godfried Toussaint",

year = "1995",

doi = "10.1007/3-540-60220-8_64",

language = "English (US)",

isbn = "3540602208",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "218--227",

editor = "Akl, {Selim G.} and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings",

}

TY - GEN

T1 - Quadrangulations of planar sets

AU - Toussaint, Godfried

PY - 1995

Y1 - 1995

N2 - Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if 5 is a polygon, or the interior of the convex hull of S, if 5 is a set of points, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or sets of points admit quadrangulations, even when the quadrangles are not required to be convex (convex quadrangulations). In this paper we briefly survey some recent results concerning the characterization of those planar sets that always admit quadrangulations (convex and non-convex) as well as some related computational problems.

AB - Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if 5 is a polygon, or the interior of the convex hull of S, if 5 is a set of points, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or sets of points admit quadrangulations, even when the quadrangles are not required to be convex (convex quadrangulations). In this paper we briefly survey some recent results concerning the characterization of those planar sets that always admit quadrangulations (convex and non-convex) as well as some related computational problems.

UR - http://www.scopus.com/inward/record.url?scp=79960588154&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960588154&partnerID=8YFLogxK

U2 - 10.1007/3-540-60220-8_64

DO - 10.1007/3-540-60220-8_64

M3 - Conference contribution

AN - SCOPUS:79960588154

SN - 3540602208

SN - 9783540602200

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 218

EP - 227

BT - Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings

A2 - Akl, Selim G.

A2 - Dehne, Frank

A2 - Sack, Jörg-Rüdiger

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - 4th Workshop on Algorithms and Data Structures, WADS 1995

Y2 - 16 August 1995 through 18 August 1995

ER -

Quadrangulations of planar sets

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this