Article

Free access

Finding the optimal shadows of a convex polytope

Authors:

Michael McKenna,

Raimund SeidelAuthors Info & Claims

SCG '85: Proceedings of the first annual symposium on Computational geometry

Pages 24 - 28

https://doi.org/10.1145/323233.323237

Published: 01 June 2019 Publication History

PDF eReader

Abstract

Let P be a convex polytope in R^d. We discuss the problem of placing a light source at infinity so as to minimize or maximize the shadow area of the polytope. By shadow area we mean the (d-1)-volume of the orthogonal projection of P on a hyperplane normal to the direction of illumination. Let n be the number of (d-1)-dimensional facets of the polytope. We exhibit two algorithms for finding the optimal placement of the light source. One algorithm uses O(n^d-1) space and time to find the optimal placement. The other uses O(n) space to find the optimal placement in O(n^d-1 log n) time. Also, we present an interesting result relating the minimum and maximum shadow areas of P to the radii of the inscribed and circumscribed sphere of a zonotope derived from P.

References

[1]

{1} Edelsbrunner, H., Private communication.

Google Scholar

[2]

{2} Edelsbrunner, H., O'Rourke, J., Seidel, R., "Constructing arrangements of lines and hyperplanes with applications", to appear in the SIAM Journal on Computing ; full version of reference {3}.

Digital Library

Google Scholar

[3]

{3} Edelsbrunner, H., O'Rourke, J., Seidel, R., "Constructing arrangements of lines and hyperplanes with applications", Proceedings of the 24th Foundations of Computer Science Conference, pp. 83-91, November 1983.

Google Scholar

[4]

{4} Grunbaum, B., Convex polytopes, Wiley Interscience, 1967.

Google Scholar

[5]

{5} Toussaint, G.T., "Solving geometric problems with the 'rotating calipers'", Proceedings of IEEE MELECON '83, Athens, Greece, May 1983.

Google Scholar

[6]

{6} vanLeeuwen, J., Private communication.

Google Scholar

Cited By

View all

Alam MHasan M(2008)Computing nice projections of convex polyhedraProceedings of the 2nd international conference on Algorithms and computation10.5555/1787651.1787665(111-119)Online publication date: 7-Feb-2008
https://dl.acm.org/doi/10.5555/1787651.1787665
Alam MHasan M(2008)Computing Nice Projections of Convex PolyhedraWALCOM: Algorithms and Computation10.1007/978-3-540-77891-2_11(111-119)Online publication date: 2008
https://doi.org/10.1007/978-3-540-77891-2_11
Bose PRamos PGomez FToussaint G(2005)Drawing nice projections of objects in spaceGraph Drawing10.1007/BFb0021790(52-63)Online publication date: 17-Jun-2005
https://doi.org/10.1007/BFb0021790
Show More Cited By

Finding the optimal shadows of a convex polytope
1. Mathematics of computing
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
On the cut polytope

The cut polytopePC(G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofPC(G). We describe three methods with which new facet-defining inequalities ofPC(G) ...
Lifting facets of the cut polytope

The cut polytope P"c(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. We give a sufficient condition for an inequality defining a facet of P"c(G) to define a facet of the cut polytope of a graph containing G ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '85: Proceedings of the first annual symposium on Computational geometry

June 1985

322 pages

ISBN:0897911636

DOI:10.1145/323233

Chairman:
Joseph O'Rourke
Johns Hopkins Univ., Baltimore, MD

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: 01 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCG85

Sponsor:

SCG85: The 1st Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry 1985

June 5 - 7, 1985

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
433
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)14

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Alam MHasan M(2008)Computing nice projections of convex polyhedraProceedings of the 2nd international conference on Algorithms and computation10.5555/1787651.1787665(111-119)Online publication date: 7-Feb-2008
https://dl.acm.org/doi/10.5555/1787651.1787665
Alam MHasan M(2008)Computing Nice Projections of Convex PolyhedraWALCOM: Algorithms and Computation10.1007/978-3-540-77891-2_11(111-119)Online publication date: 2008
https://doi.org/10.1007/978-3-540-77891-2_11
Bose PRamos PGomez FToussaint G(2005)Drawing nice projections of objects in spaceGraph Drawing10.1007/BFb0021790(52-63)Online publication date: 17-Jun-2005
https://doi.org/10.1007/BFb0021790
Majhi JGupta PJanardan R(2005)Computing a flattest, undercut-free parting line for a convex polyhedron, with application to mold designApplied Computational Geometry Towards Geometric Engineering10.1007/BFb0014489(109-120)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0014489
Majhi JJanardan RSmid MGupta P(2005)On some geometric optimization problems in layered manufacturingAlgorithms and Data Structures10.1007/3-540-63307-3_54(136-149)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63307-3_54
Nurmi OSack J(2005)Separating a polyhedron by one translation from a set of obstaclesGraph-Theoretic Concepts in Computer Science10.1007/3-540-50728-0_44(202-212)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-50728-0_44
Bose PGómez FRamos PToussaint G(1999)Drawing Nice Projections of Objects in SpaceJournal of Visual Communication and Image Representation10.1006/jvci.1999.041510:2(155-172)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1006/jvci.1999.0415
Hudson TManocha DCohen JLin MHoff KZhang HBoissonnat J(1997)Accelerated occlusion culling using shadow frustaProceedings of the thirteenth annual symposium on Computational geometry10.1145/262839.262847(1-10)Online publication date: 1-Aug-1997
https://dl.acm.org/doi/10.1145/262839.262847
Gritzmann PKlee V(1994)On the Complexity of Some Basic Problems in Computational ConvexityPolytopes: Abstract, Convex and Computational10.1007/978-94-011-0924-6_17(373-466)Online publication date: 1994
https://doi.org/10.1007/978-94-011-0924-6_17
Plantinga HDyer C(1990)Visibility, occlusion, and the aspect graphInternational Journal of Computer Vision10.1007/BF000549195:2(137-160)Online publication date: 1-Nov-1990
https://dl.acm.org/doi/10.1007/BF00054919
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

On the cut polytope

Lifting facets of the cut polytope