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

doi:10.1109/FSCS.1990.89543

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

1 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. In this paper we address the problem of estimating how many such cuts are always sufficient. We also consider a few related algorithmic and combinatorial geometry problems.

Original language	English (US)
Pages (from-to)	242-251
Number of pages	10
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/FSCS.1990.89543
State	Published - 1990
Externally published	Yes
Event	Proceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA Duration: Oct 22 1990 → Oct 24 1990

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/FSCS.1990.89543

Cite this

@article{2246ec8bcbce4861ac9603ac16f59501,

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. In this paper we address the problem of estimating how many such cuts are always sufficient. We also consider a few related algorithmic and combinatorial geometry problems.",

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

note = "Publisher Copyright: {\textcopyright} 1990 IEEE Computer Society. All rights reserved.; Proceedings of the 31st Annual Symposium on Foundations of Computer Science ; Conference date: 22-10-1990 Through 24-10-1990",

year = "1990",

doi = "10.1109/FSCS.1990.89543",

language = "English (US)",

pages = "242--251",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

publisher = "IEEE Computer Society",

}

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

PY - 1990

Y1 - 1990

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. In this paper we address the problem of estimating how many such cuts are always sufficient. We also consider a few related algorithmic and combinatorial geometry problems.

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. In this paper we address the problem of estimating how many such cuts are always sufficient. We also consider a few related algorithmic and combinatorial geometry problems.

UR - https://www.scopus.com/pages/publications/105031765000

UR - https://www.scopus.com/pages/publications/105031765000#tab=citedBy

U2 - 10.1109/FSCS.1990.89543

DO - 10.1109/FSCS.1990.89543

M3 - Conference article

AN - SCOPUS:105031765000

SN - 0272-5428

SP - 242

EP - 251

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings of the 31st Annual Symposium on Foundations of Computer Science

Y2 - 22 October 1990 through 24 October 1990

ER -

Counting and Cutting Cycles of Lines and Rods in Space

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this