Online Delaunay Triangulation Using the Quad-Edge Data Structure

被引：0
|
作者：
Mandal, Chintan
Agarwal, Suneeta
机构：
来源：
ADVANCES IN COMPUTING AND INFORMATION TECHNOLOGY | 2011年 / 198卷
关键词：
Online algorithms; Delaunay triangulation; Convex Hull; Quad-Edge data structure;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Previous works involving the Online Delaunay triangulation problem required that the incoming request lies within the triangulation or a predefined initial triangulation framework, which will contain all the incoming points. No mention is made for Online Delaunay triangulation when the request point lies outside the triangulation, which also happens to be the unbounded side of the Convex Hull of the triangulation. In this work, we give a solution for the Online Delaunay triangulation Problem for incoming request points lying in the unbounded side of the Convex Hull bounding the Delaunay triangulation as well for points lying inside the triangulation. We use the Quad-Edge data structure for implementing the Delaunay triangulation.
引用
收藏
页码：132 / 141
页数：10
相关论文
共 50 条
  • [41] Direction Control Using Delaunay Triangulation for Coverage Improvement in Directional Sensor Networks
    Sung, Tien-Wen
    Lu, You-Te
    Lin, Fu-Tian
    Yang, Chu-Sing
    2015 THIRD INTERNATIONAL CONFERENCE ON ROBOT, VISION AND SIGNAL PROCESSING (RVSP), 2015, : 290 - 293
  • [42] 3D Interpolation of Image Elastic Deformation Using Delaunay Triangulation
    Yang, Xuan
    Pei, Jihong
    2009 3RD INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICAL ENGINEERING, VOLS 1-11, 2009, : 1994 - +
  • [43] On the Guidance of Multiple UAV using a Centralized Formation Control Scheme and Delaunay Triangulation
    Alexandre Santos Brandão
    Mário Sarcinelli-Filho
    Journal of Intelligent & Robotic Systems, 2016, 84 : 397 - 413
  • [44] Using Voronoi Tessellation and Delaunay Triangulation to Evaluate Spatial Uniformity of Particle Distribution
    Peng, Yahui
    Wang, Xian'gang
    Du, Yi
    Chen, Houjin
    INTERNATIONAL CONFERENCE MACHINERY, ELECTRONICS AND CONTROL SIMULATION, 2014, 614 : 413 - 416
  • [45] d-Simplexed: Adaptive Delaunay Triangulation or Performance Modeling and Prediction on Big Data Analytics
    Chen, Yuxing
    Goetsch, Peter
    Hoque, Mohammad A.
    Lu, Jiaheng
    Tarkoma, Sasu
    IEEE TRANSACTIONS ON BIG DATA, 2022, 8 (02) : 458 - 469
  • [46] An incremental algorithm for simultaneous construction of 2D Voronoi diagram and Delaunay triangulation based on a face-based data structure
    Shivanasab, Pooya
    Abbaspour, Rahim Ali
    ADVANCES IN ENGINEERING SOFTWARE, 2022, 169
  • [47] An adaptive and rapid 3D Delaunay triangulation for randomly distributed point cloud data
    Tianyun Su
    Wen Wang
    Haixing Liu
    Zhendong Liu
    Xinfang Li
    Zhen Jia
    Lin Zhou
    Zhuanling Song
    Ming Ding
    Aiju Cui
    The Visual Computer, 2022, 38 : 197 - 221
  • [48] AN AUTOMATIC TECHNIQUE FOR DECIDUOUS TREES DETECTION IN HIGH DENSITY LIDAR DATA BASED ON DELAUNAY TRIANGULATION
    Marinelli, Daniele
    Paris, Claudia
    Bruzzone, Lorenzo
    2019 IEEE INTERNATIONAL GEOSCIENCE AND REMOTE SENSING SYMPOSIUM (IGARSS 2019), 2019, : 94 - 97
  • [49] Multiple UAV Guidance Using the Multi-Layer Control Scheme and Delaunay Triangulation
    Brandao, Alexandre S.
    Barbosa, Joao Paulo A.
    Mendoza, Valentin
    Sarcinelli-Filho, Mario
    2014 2ND BRAZILIAN ROBOTICS SYMPOSIUM (SBR) / 11TH LATIN AMERICAN ROBOTICS SYMPOSIUM (LARS) / 6TH ROBOCONTROL WORKSHOP ON APPLIED ROBOTICS AND AUTOMATION, 2014, : 113 - 117
  • [50] High resolution image formation from low resolution frames using Delaunay triangulation
    Lertrattanapanich, S
    Bose, NK
    IEEE TRANSACTIONS ON IMAGE PROCESSING, 2002, 11 (12) : 1427 - 1441
12345