Radiosity algorithms running in sub-quadratic time

被引：0

作者：

Szirmay-Kalos, L ^{[1
]}

Foris, T ^{[1
]}

机构：

[1] Tech Univ Budapest, Dept Proc Control, H-1111 Budapest, Hungary

来源：

WSCG '97: THE FIFTH INTERNATIONAL CONFERENCE IN CENTRAL EUROPE ON COMPUTER GRAPHICS AND VISUALIZATION '97, CONFERENCE PROCEEDINGS, VOL 1-4 | 1997年

关键词：

radiosity method; iterative techniques; transillumination; complexity; painter's algorithm;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This par,er presents an iterative radiosity algorithm that is capable to determine the radiosity of the patches in O(n log n) time and using only O(n) space. The basic idea is to compute the radiosity updates of all patches in a single direction parallely, requiring only one complete solution of the visibility problem per directions. The visibility problem is solved by painter's algorithm that is responsible for the O(n log n) time complexity, and thus it does not require large amount of z-buffer memory.

引用

页码：552 / 561

页数：10

共 50 条

[11] Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Chakraborty, Diptarka
Das, Debarati
Goldenberg, Elazar
Koucky, Michal
Saks, Michael
2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018, : 979 - 990
[12] Matrix-Vector Multiplication in Sub-Quadratic Time (Some Preprocessing Required)
Williams, Ryan
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2007, : 995 - 1001
[13] Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
Chakraborty, Diptarka
Das, Debarati
Goldenberg, Elazar
Koucky, Michal
Saks, Michael
JOURNAL OF THE ACM, 2020, 67 (06)
[14] Range mode and range median queries in constant time and sub-quadratic space
Petersen, Holger
Grabowski, Szymon
INFORMATION PROCESSING LETTERS, 2009, 109 (04) : 225 - 228
[15] Towards sub-quadratic time and space complexity solutions for the dated tree reconciliation problem
Benjamin Drinkwater
Michael A. Charleston
Algorithms for Molecular Biology, 11
[16] A hybrid layout algorithm for sub-quadratic multidimensional scaling
Morrison, A
Ross, G
Chalmers, M
INFOVIS 2002: IEEE SYMPOSIUM ON INFORMATION VISUALIZATION 2002, 2002, : 152 - 158
[17] An old sub-quadratic algorithm for finding extremal sets
Pritchard, P
INFORMATION PROCESSING LETTERS, 1997, 62 (06) : 329 - 334
[18] Domain characterization for Schrodinger operators with sub-quadratic singularity
Metafune, Giorgio
Sobajima, Motohiro
NODEA-NONLINEAR DIFFERENTIAL EQUATIONS AND APPLICATIONS, 2025, 32 (02):
[19] Ripple Attention for Visual Perception with Sub-quadratic Complexity
Zheng, Lin
Pan, Huijie
Kong, Lingpeng
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 162, 2022,
[20] A new template for solving p-Median problems for trees in sub-quadratic time
Benkoczi, R
Bhattacharya, B
ALGORITHMS - ESA 2005, 2005, 3669 : 271 - 282

← 1 2 3 4 5 →