id
	11997
Url
	https://chloe.cnr.it/s/BiDiAr/item/11997
Resource template
	Academic Article
Resource class
	bibo:AcademicArticle
Title
	Fast topological construction of delaunay triangulations and voronoi diagrams
Creator
	Tsai, Victor J. D.
Date
	1993
Language
	eng
Abstract
	This paper describes a Convex Hull Insertion algorithm for constructing the Delaunay triangulation and the Voronoi diagram of randomly distributed points in the Euclidean plane. The implemented program on IBM-compatible personal computers takes benefits from the partitioning of data points, topological data structures of spatial primitives, and features in C++ programming language such as dynamic memory allocation and class objects. The program can handle arbitrary collections of points, and delivers several output options to link with GIS and CAD systems. Empirical results of various sets of up to 50,000 points show that the proposed algorithm speeds up the construction of both tessellations of irregular points in expected linear time.
Is Part Of
	Computers & Geosciences
Cited by
	11057
Doi
	https://doi.org/10.1016/0098-3004(93)90062-A
Issn
	0098-3004
Issue
	10
Pages
	1463-1474
Uri
	https://www.sciencedirect.com/science/article/pii/009830049390062A
Volume
	19
Homepage
	https://www.zotero.org/groups/5293298/bidiar/items/EGF44DEZ/item-list

--