Triangulating input-constrained planar point sets

Martin Held; Joseph S.B. Mitchell

doi:10.1016/j.ipl.2008.09.016

Triangulating input-constrained planar point sets

Martin Held
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

University of Salzburg

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O (n log n) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.

Original language	English
Pages (from-to)	54-56
Number of pages	3
Journal	Information Processing Letters
Volume	109
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2008.09.016
State	Published - Dec 16 2008

Keywords

Computational geometry
Constrained
Imprecision
Points
Triangulation

Access to Document

10.1016/j.ipl.2008.09.016

Cite this

@article{da92383fa08c47a8b49d225e47493b86,

title = "Triangulating input-constrained planar point sets",

abstract = "We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O (n log n) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.",

keywords = "Computational geometry, Constrained, Imprecision, Points, Triangulation",

author = "Martin Held and Mitchell, \{Joseph S.B.\}",

year = "2008",

month = dec,

day = "16",

doi = "10.1016/j.ipl.2008.09.016",

language = "English",

volume = "109",

pages = "54--56",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "1",

}

TY - JOUR

T1 - Triangulating input-constrained planar point sets

AU - Held, Martin

AU - Mitchell, Joseph S.B.

PY - 2008/12/16

Y1 - 2008/12/16

N2 - We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O (n log n) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.

AB - We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O (n log n) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.

KW - Computational geometry

KW - Constrained

KW - Imprecision

KW - Points

KW - Triangulation

UR - https://www.scopus.com/pages/publications/55149087469

U2 - 10.1016/j.ipl.2008.09.016

DO - 10.1016/j.ipl.2008.09.016

M3 - Article

AN - SCOPUS:55149087469

SN - 0020-0190

VL - 109

SP - 54

EP - 56

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Triangulating input-constrained planar point sets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this