Reconstructing hv-convex polyominoes from orthogonal projections

被引：69

作者：

Chrobak, M ^{[1
]}

Dürr, C

机构：

[1] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA

[2] Int Comp Sci Inst, Berkeley, CA 94704 USA

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 06期

基金：

美国国家科学基金会;

关键词：

combinatorial problems; discrete tomography; polyominoes;

D O I：

10.1016/S0020-0190(99)00025-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We address the problem of reconstructing a discrete 2D object, represented by a set of grid cells, from its orthogonal projections. We focus on objects called hv-convex polyominoes, which are connected objects with the property that the cells in each row and column are consecutive. The main result of this paper is a simple, O(mn min(m(2), n(2)))-time algorithm for reconstructing hv-convex polyominoes. (C) 1999 Elsevier Science B.V. kll rights reserved.

引用

页码：283 / 289

页数：7

共 9 条

[1] LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS [J].

ASPVALL, B ;

PLASS, MF ;

TARJAN, RE .

INFORMATION PROCESSING LETTERS, 1979, 8 (03) :121-123

[2] Reconstructing convex polyominoes from horizontal and vertical projections [J].

Barcucci, E ;

DelLungo, A ;

Nivat, M ;

Pinzani, R .

THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) :321-347

[3]

BARCUCCI E, IN PRESS INT J IMAGI

[4] MATRICES OF ZEROS AND ONES WITH FIXED ROW AND COLUMN SUM VECTORS [J].

BRUALDI, RA .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1980, 33 (OCT) :159-231

[5]

Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048

[6]

GARDNER RJ, 1997, 9705012 TU MUNCH

[7] THE RECONSTRUCTION OF 2-DIRECTIONALLY CONNECTED BINARY PATTERNS FROM THEIR 2 ORTHOGONAL PROJECTIONS [J].

KUBA, A .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1984, 27 (03) :249-265

[8]

Ryser H. J., 1963, COMBINATORIAL MATH, DOI DOI 10.5948/UPO9781614440147

[9]

WOEGINGER GJ, 1996, SFB65 TU GRAZ

← 1 →