Reconstructing orthogonal polyhedra from putative vertex sets

被引：12
作者：
Biedl, Therese [2 ]
Genc, Burkay [1 ]
机构：
[1] Izmir Univ Econ, Fac Engn & Comp Sci, Izmir, Turkey
[2] Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2011年 / 44卷 / 08期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Reconstruction; Vertex set; Orthogonal polyhedra;
D O I：
10.1016/j.comgeo.2011.04.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper we study the problem of reconstructing orthogonal polyhedra from a putative vertex set, i.e., we are given a set of points and want to find an orthogonal polyhedron for which this is the set of vertices. This is well-studied in 2D; we mostly focus on 3D, and on the case where the given set of points may be rotated beforehand. We obtain fast algorithms for reconstruction in the case where the answer must be orthogonally convex. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：409 / 417
页数：9
相关论文
共 16 条
  • [1] On polyhedra induced by point sets in space
    Agarwal, Pankaj K.
    Hurtado, Ferran
    Toussaint, Godfried T.
    Trias, Joan
    [J]. DISCRETE APPLIED MATHEMATICS, 2008, 156 (01) : 42 - 54
  • [2] Aguilera A., 1997, Proceedings. Fourth Symposium on Solid Modeling and Applications, P56, DOI 10.1145/267734.267754
  • [3] DOT PATTERN PROCESSING USING VORONOI NEIGHBORHOODS
    AHUJA, N
    [J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1982, 4 (03) : 336 - 343
  • [4] Point set surfaces
    Alexa, M
    Behr, J
    Cohen-Or, D
    Fleishman, S
    Levin, D
    Silva, CT
    [J]. VISUALIZATION 2001, PROCEEDINGS, 2001, : 21 - 28
  • [5] [Anonymous], 1998, THESIS U POLITECNICA
  • [6] Bournez O, 1999, LECT NOTES COMPUT SC, V1569, P46
  • [7] Gr?nbaum B., 1994, GEOMBINATORICS, V3, P83
  • [8] KIRKPATRICK DG, 1985, P 1 ANN S COMP GEOM, P89, DOI DOI 10.1145/323233.323246
  • [9] Löffler M, 2009, LECT NOTES COMPUT SC, V5417, P313, DOI 10.1007/978-3-642-00219-9_30
  • [10] O'Callaghan J.F., 1974, COMPUT VISION GRAPH, V3, P141, DOI [10.1016/S0146-664X(74)80004-3, DOI 10.1016/S0146-664X(74)80004-3]
12