research-article

An efficient PILP algorithm for 3D region guarding and star decomposition

Authors:

Wuyi Yu,

Xin LiAuthors Info & Claims

SIGGRAPH '11: ACM SIGGRAPH 2011 Posters

Article No.: 59, Page 1

https://doi.org/10.1145/2037715.2037782

Published: 07 August 2011 Publication History

Get Access

Abstract

We propose an efficient algorithm to compute 3D region guarding and star decomposition. A star decomposition partitions a 3D region to a set of sub-regions, each of which is visible from an interior point and is called a star shape. Star decomposition is closely related to the well known gallery guarding problem [Chvatal 1975]. Despite their broad applications in graphics and robotics, 3D region guarding and star decomposition are highly challenging and have been little explored.

References

[1]

Chvatal, V. 1975. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory Series B 18, 39--41.

Crossref

Google Scholar

[2]

Lien, J.-M. 2007. Approximate star-shaped decomposition of point set data. In Eurographics Symposium on Point-Based Graphics, 1--8.

Google Scholar

Index Terms

An efficient PILP algorithm for 3D region guarding and star decomposition
1. Computing methodologies
  1. Computer graphics
2. General and reference

Recommendations

Efficient Guarding of Polygons and Terrains
Frontiers in Algorithmics
Abstract
In this paper, we study the Efficient Guarding problem - a variant of the well studied Art Gallery Problem in computational geometry. A given polygon P is considered to be guarded efficiently by a guard set G if every point in P is seen by exactly ...
Efficient VLSI architecture of 3D discrete transformation
Abstract
Discrete transforms are used in many signal processing applications such as audio compression, image compression, video compression, high efficiency video coding (HEVC), and so on. This paper proposes a generic VLSI architecture for ...
Highlights
- This paper proposes an architecture for various (N×N×N)-point discrete transforms.
Improvement in protein-coding region identification based on sliding window trigonometric fast transforms using Singular Value Decomposition

In this paper, the performance of various sliding window trigonometric fast transforms for identification of protein coding regions has been analysed at the nucleotide level. It is found that, Short-Time Discrete Fourier Transform (ST-DFT) gives better ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGGRAPH '11: ACM SIGGRAPH 2011 Posters

August 2011

92 pages

ISBN:9781450309714

DOI:10.1145/2037715

Conference Chair:
Dan Wexler

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

SIGGRAPH '11

Sponsor:

SIGGRAPH

SIGGRAPH '11: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 7 - 11, 2011

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
58
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Efficient Guarding of Polygons and Terrains

Efficient VLSI architecture of 3D discrete transformation

Improvement in protein-coding region identification based on sliding window trigonometric fast transforms using Singular Value Decomposition