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 条
  • [21] STL file generation from measured point data by segmentation and Delaunay triangulation
    Lee, SH
    Kim, HC
    Hur, SM
    Yang, DY
    COMPUTER-AIDED DESIGN, 2002, 34 (10) : 691 - 704
  • [22] Curve detection using Delaunay triangulation based on perceptual grouping factors
    Takagi, Takamitsu
    Saitoh, Fumihiko
    ELECTRONICS AND COMMUNICATIONS IN JAPAN, 2012, 95 (07) : 19 - 28
  • [23] Numerical conformal mapping using cross-ratios and Delaunay triangulation
    Driscoll, TA
    Vavasis, SA
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1998, 19 (06): : 1783 - 1803
  • [24] Skin Cancer Classification using Delaunay Triangulation and Graph Convolutional Network
    Sunarya, Caroline Angelina
    Siswanto, Jocelyn Verna
    Cam, Grace Shirley
    Kurniadi, Felix Indra
    INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 2023, 14 (06) : 797 - 805
  • [25] Authentication Based on the Image Encryption using Delaunay Triangulation and Catalan Objects
    Selimovic, Faruk
    Stanimirovic, Predrag
    Saracevic, Muzafer
    Selimi, Aybeyan
    Krtolica, Predrag
    ACTA POLYTECHNICA HUNGARICA, 2020, 17 (06) : 207 - 224
  • [26] An Automated System for Offline Signature Verification and Identification Using Delaunay Triangulation
    Jan, Zahoor
    Muhammad, Hayat
    Rafiq, Muhammad
    Zada, Noor
    NEW CONTRIBUTIONS IN INFORMATION SYSTEMS AND TECHNOLOGIES, VOL 1, PT 1, 2015, 353 : 653 - 663
  • [27] A Hierarchical Matching Method for Vectorial Road Networks Using Delaunay Triangulation
    Zuo, Zejun
    Yang, Lin
    An, Xiaoya
    Zhen, Wenjie
    Qian, Haoyue
    Dai, Songling
    ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION, 2020, 9 (09)
  • [28] On the Necessity of Using Delaunay Triangulation Substrate in Greedy Routing Based Networks
    Ghaffari, Mohsen
    Hariri, Behnoosh
    Shirmohammadi, Shervin
    IEEE COMMUNICATIONS LETTERS, 2010, 14 (03) : 266 - 268
  • [29] Calculation of mean central dose in interstitial brachytherapy using Delaunay triangulation
    Astrahan, MA
    Streeter, OE
    Jozsef, G
    MEDICAL PHYSICS, 2001, 28 (06) : 1016 - 1023
  • [30] STL file generation with data reduction by the Delaunay triangulation method in reverse engineering
    Hur, SM
    Kim, HC
    Lee, SH
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2002, 19 (09): : 669 - 678
12345