Counting and cutting cycles of lines and rods in space

Bernard Chazelle; Herbert Edelsbrunner; Leonidas J. Guibas; Richard Pollack; Raimund Seidel; Micha Sharir; Jack Snoeyink

Counting and cutting cycles of lines and rods in space

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink

Research output: Contribution to journal › Conference article › peer-review

3 Scopus citations

Abstract

A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.

Original language	English (US)
Pages (from-to)	242-251
Number of pages	10
Journal	IEEE Transactions on Industry Applications
Volume	27
Issue number	1 pt 1
State	Published - Jan 1991
Externally published	Yes
Event	1989 Industry Applications Society Annual Meeting - San Diego, CA, USA Duration: Oct 1 1989 → Oct 5 1989

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Industrial and Manufacturing Engineering
Electrical and Electronic Engineering

Cite this

@article{34a2e08ce40049129228fa7c2d324dc8,

title = "Counting and cutting cycles of lines and rods in space",

abstract = "A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.",

author = "Bernard Chazelle and Herbert Edelsbrunner and Guibas, {Leonidas J.} and Richard Pollack and Raimund Seidel and Micha Sharir and Jack Snoeyink",

note = "Funding Information: Communicated by Kurt Mehlhorn Submitted 2 October 1990 Accepted 1 February 1991 * Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-9002352. Herbert Edelsbrunner acknowledges the support of the National Science Foundation under grants CCR-8714565 and CCR-8921421. Richard Pollack was supported in part by NSF grant CCR-8901484, NSA grant MDA904-89-H-2030, and DIMACS, a Science and Technology Center under NSF grant STC88-09648. Raimund Seidel acknowledges support by NSF grant CCR-8809040. Mich Sharir was partially supported by the Office of Naval Research under Grant N00014-87-K-0129, by the National Science Foundation under Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation and the Fund for Basic Research administered by the Israeli Academy of Sciences.; 1989 Industry Applications Society Annual Meeting ; Conference date: 01-10-1989 Through 05-10-1989",

year = "1991",

month = jan,

language = "English (US)",

volume = "27",

pages = "242--251",

journal = "IEEE Transactions on Industry Applications",

issn = "0093-9994",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1 pt 1",

}

TY - JOUR

T1 - Counting and cutting cycles of lines and rods in space

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas J.

AU - Pollack, Richard

AU - Seidel, Raimund

AU - Sharir, Micha

AU - Snoeyink, Jack

N1 - Funding Information: Communicated by Kurt Mehlhorn Submitted 2 October 1990 Accepted 1 February 1991 * Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-9002352. Herbert Edelsbrunner acknowledges the support of the National Science Foundation under grants CCR-8714565 and CCR-8921421. Richard Pollack was supported in part by NSF grant CCR-8901484, NSA grant MDA904-89-H-2030, and DIMACS, a Science and Technology Center under NSF grant STC88-09648. Raimund Seidel acknowledges support by NSF grant CCR-8809040. Mich Sharir was partially supported by the Office of Naval Research under Grant N00014-87-K-0129, by the National Science Foundation under Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation and the Fund for Basic Research administered by the Israeli Academy of Sciences.

PY - 1991/1

Y1 - 1991/1

N2 - A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.

AB - A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.

UR - http://www.scopus.com/inward/record.url?scp=0025742009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025742009&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0025742009

SN - 0093-9994

VL - 27

SP - 242

EP - 251

JO - IEEE Transactions on Industry Applications

JF - IEEE Transactions on Industry Applications

IS - 1 pt 1

T2 - 1989 Industry Applications Society Annual Meeting

Y2 - 1 October 1989 through 5 October 1989

ER -

Counting and cutting cycles of lines and rods in space

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this