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 条
  • [31] Translation, Scaling and Rotation Invariant Spot Matching using Delaunay Triangulation
    Yukhuu, Ankhbayar
    Sup, Hwang Young
    PROCEEDINGS OF THE 8TH WSEAS INTERNATIONAL CONFERENCE ON APPLIED COMPUTER SCIENCE (ACS'08): RECENT ADVANCES ON APPLIED COMPUTER SCIENCE, 2008, : 285 - +
  • [32] A novel method of Delaunay triangulation and a custom graph neural network for treetop detection using airborne LiDAR data
    Jia, Jiaxuan
    Zhang, Lei
    Yin, Kai
    Soergel, Uwe
    REMOTE SENSING LETTERS, 2025, 16 (04) : 376 - 388
  • [33] PREDICTING SYSTEM PERFORMANCE BY INTERPOLATION USING A HIGH-DIMENSIONAL DELAUNAY TRIANGULATION
    Chang, Tyler H.
    Watson, Layne T.
    Lux, Thomas C. H.
    Bernard, Jon
    Li, Bo
    Xu, Li
    Back, Godmar
    Butt, Ali R.
    Cameron, Kirk W.
    Hong, Yili
    HIGH PERFORMANCE COMPUTING SYMPOSIUM (HPC 2018), 2018, 50 (04):
  • [34] Identifying parent locations in the Neyman-Scott process using Delaunay triangulation
    Najari, Nader
    Vahidi Asl, Mohammad Q.
    Jalilian, Abdollah
    COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION, 2022, 51 (10) : 6058 - 6070
  • [35] COMPUTATION OF 3D SKELETONS USING A GENERALIZED DELAUNAY TRIANGULATION TECHNIQUE
    REDDY, JM
    TURKIYYAH, GM
    COMPUTER-AIDED DESIGN, 1995, 27 (09) : 677 - 694
  • [36] Image compression using the distance transform on curved space (DTOCS) and Delaunay triangulation
    Toivanen, PJ
    Vepsäläinen, AM
    Parkkinen, JPS
    PATTERN RECOGNITION LETTERS, 1999, 20 (10) : 1015 - 1026
  • [37] The extraction of road boundary from crowdsourcing trajectory using constrained delaunay triangulation
    Yang W.
    Ai T.
    Cehui Xuebao/Acta Geodaetica et Cartographica Sinica, 2017, 46 (02): : 237 - 245
  • [38] Refractometric Properties of a TFBG Sensor Demodulated Using α-Shape Modified Delaunay Triangulation
    Fazzi, Luigi
    Groves, Roger M.
    OPTICS, 2021, 2 (02): : 113 - 133
  • [39] Dots and Incipient based Fingerprint Matching Scheme using FMM and Delaunay Triangulation
    Swain, Satyabrata
    Majhi, Banshidhar
    Dash, Ratnakar
    Sa, Pankaj Kumar
    2014 9TH INTERNATIONAL CONFERENCE ON INDUSTRIAL AND INFORMATION SYSTEMS (ICIIS), 2014, : 168 - 173
  • [40] On the Guidance of Multiple UAV using a Centralized Formation Control Scheme and Delaunay Triangulation
    Brandao, Alexandre Santos
    Sarcinelli-Filho, Mario
    JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS, 2016, 84 (1-4) : 397 - 413
12345