On the Construction of Planar Embedding for a Class of Orthogonal Polyhedra

被引：0

作者：

Karmakar, Nilanjana ^{[1
]}

Biswas, Arindam ^{[2
]}

Nandy, Subhas C. ^{[3
]}

Bhattacharya, Bhargab B. ^{[4
]}

机构：

[1] St Thomas Coll Engn & Technol, Dept Informat Technol, Kolkata, India

[2] Indian Inst Engn Sci & Technol, Dept Informat Technol, Sibpur, India

[3] Indian Stat Inst, Adv Comp & Microelect Unit, Kolkata, India

[4] Indian Inst Technol Kharagpur, Dept Comp Sci & Engn, Kharagpur, W Bengal, India

来源：

COMBINATORIAL IMAGE ANALYSIS, IWCIA 2022 | 2023年 / 13348卷

关键词：

Orthogonal polyhedron; Planar graph; Graph drawing; GRAPHS; ALGORITHM; THEOREM;

D O I：

10.1007/978-3-031-23612-9_6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

2D-representations of 3D digital objects find versatile applications to computer vision, robotics, medical imaging, and in discrete geometry. This work presents an algorithm for constructing a planar embedding with only straight-line edges for a general non-intersecting orthogonal polyhedron that has genus 0. We discover certain characterizations of vertices and edges of a polyhedron that lead to efficient graph-drawing on the 2D plane. The original orthogonal polyhedron can be fully reconstructed from this graph provided the information regarding the coordinates of vertices, are preserved. The time complexity of the proposed embedding is linear in the number of edges of the orthogonal polyhedron.

引用

页码：84 / 104

页数：21

共 50 条

[21] Construction of σ-orthogonal polynomials and gaussian quadrature formulas
Shi, Ying Guang
Xu, Guoliang
ADVANCES IN COMPUTATIONAL MATHEMATICS, 2007, 27 (01) : 79 - 94
[22] Construction of σ-orthogonal polynomials and gaussian quadrature formulas
Ying Guang Shi
Guoliang Xu
Advances in Computational Mathematics, 2007, 27 : 79 - 94
[23] Toughness and Hamiltonicity of a class of planar graphs
Gerlach, T
DISCRETE MATHEMATICS, 2004, 286 (1-2) : 61 - 65
[24] Bend minimization in planar orthogonal drawings using integer programming
Mutzel, Petra
Weiskircher, Rene
SIAM JOURNAL ON OPTIMIZATION, 2006, 17 (03) : 665 - 687
[25] Construction of symmetric orthogonal designs with deep Q-network and orthogonal complementary design
Lai, Jianfa
Weng, Lin-Chen
Peng, Xiaoling
Fang, Kai-Tai
COMPUTATIONAL STATISTICS & DATA ANALYSIS, 2022, 171
[26] Construction of robust class hierarchies
Frick, A
Goos, G
Neumann, R
Zimmermann, W
SOFTWARE-PRACTICE & EXPERIENCE, 2000, 30 (05): : 481 - 543
[27] Planar embedding of trees on point sets without the general position assumption
Asgharian Sardroud, Asghar
Bagheri, Alireza
TURKISH JOURNAL OF MATHEMATICS, 2015, 39 (06) : 820 - 829
[28] Construction of planar 4-connected triangulations
Brinkmann, Gunnar
Larson, Craig
Souffriau, Jasper
Van Cleemput, Nico
ARS MATHEMATICA CONTEMPORANEA, 2015, 9 (02) : 145 - 149
[29] A New Class of Reciprocal-Orthogonal Parametric Transforms
Bouguezel, Saad
Ahmad, M. Omair
Swamy, M. N. S.
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2009, 56 (04) : 795 - 805
[30] A sufficient condition for a planar graph to be class 1
Wang, Weifan
Chen, Yongzhu
THEORETICAL COMPUTER SCIENCE, 2007, 385 (1-3) : 71 - 77

← 1 2 3 4 5 →