triangulation verification

[Olivier Devillers]

> Some time ago, I came across a paper which dealt with the problem
> of verifying whether a given collection of triangles is a triangulation
> of a given polygon.


The computational geometry bibliography can be download at
ftp.cs.usask.ca

query can be sent to
http://www-ma2.upc.es/~geomc/geombib/geombibe.html
http://www.cs.uu.nl/geobook/geom.html



@article{mnssssu-cgpvg-99
, author =      "K. Mehlhorn and S. N{\"a}her and M. Seel and R. Seidel and T. S
chilz and S. Schirra and C. Uhrig"
, title =       "Checking Geometric Programs or Verification of Geometric Struct
ures"
, journal =     "Comput. Geom. Theory Appl."
, volume =      12
, number =      "1--2"
, year =        1999
, pages =       "85--103"
, succeeds =    "mnssssu-cgpvg-96"
, update =      "99.07
}


@article{dlpt-ccpps-98
, author =      "Olivier Devillers and Giuseppe Liotta and Franco P. Preparata a
nd Roberto Tamassia"
, title =       "Checking the Convexity of Polytopes and the Planarity of Subdiv
isions"
, journal =     "Comput. Geom. Theory Appl."
, volume =      11
, year =        1998
, pages =       "187--208"
, url = "http://www-sop.inria.fr/prisme/biblio/search.html"
, keywords =    "graph drawing, planar, straight-line, checking"
, succeeds =    "dlpt-ccpps-97"
, cites =       "-dcgs-, bbdgt-ccgg-97, bo-arcgi-79, bk-dpcw-95, b-ecvdl-96, c-t
splt-91a, dtv-olcpt-95, dtv-olcpt-95t, dv-aptg-96, f-slrpg-48, glm-othsr-96, h-g
t-72, ht-ept-74, k-eops-88, ll-abgtc-87, lpt-rpqid-97, lpt-rpqid-99, mn-cgs-96, 
mnssssu-cgpvg-96, mnssssu-cgpvg-97, swm-ccr-95, y-tegc-97"
, update =      "99.11 devillers, 99.03 devillers, 98.11 tamassia"
, abstract =    "This paper considers the problem of verifying the correctness o
f geometric structures. In particular, we design simple optimal checkers for con
vex polytopes in two and higher dimensions, and for various types of planar subd
ivisions, such as triangulations, Delaunay triangulations, and convex subdivisio
ns. Their performance is analyzed also in terms of the algorithmic degree, which
 characterizes the arithmetic precision required."
}



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.