M. de Berg, O. Devillers, M. van Kreveld, O. Schwarzkopf, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Manuscript, 1995.

Google Scholar

[4]

S. W. Dharmadhikari and K. Jogdeo. A characterization of convexity and central symmetry for planar polygonal sets. Israel J. Math., 15:356-366, 1973.

Crossref

Google Scholar

[5]

L. Khachiyan. Complexity of polytope volume computation. In J. Pach, editor, New Trends in Discrete and Computational Geometry, pages 91-101. Springer~Verlag, 1993.

Crossref

Google Scholar

[6]

J. R. Sangwine-Yager. Mixed volumes. In P. M. Gruber and J. M. Wills, editors, Handbook of Convex Geometry, volume A, pages 43-71. Elsevier, 1993.

Google Scholar

[7]

T. C. Shermer. A linear algorithm for bisecting a polygon. IPL, 41:135-140, 1992.

Digital Library

Google Scholar

Cited By

View all

Har-Peled SRoy S(2017)Approximating the Maximum Overlap of Polygons under TranslationAlgorithmica10.1007/s00453-016-0152-978:1(147-165)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s00453-016-0152-9
Har-Peled SRoy S(2014)Approximating the Maximum Overlap of Polygons under TranslationAlgorithms - ESA 201410.1007/978-3-662-44777-2_45(542-553)Online publication date: 2014
https://doi.org/10.1007/978-3-662-44777-2_45
Wolovick ND'Argenio PQu H(2009)Optimizing Probabilities of Real-Time Test Case ExecutionProceedings of the 2009 International Conference on Software Testing Verification and Validation10.1109/ICST.2009.59(446-455)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/ICST.2009.59
Show More Cited By

Index Terms

On the sectional area of convex polytopes
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Randomness, geometry and discrete structures
    1. Computational geometry

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^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...
Properties of convex polytopes

Comments

Information & Contributors

Information

Published In

SCG '96: Proceedings of the twelfth annual symposium on Computational geometry

May 1996

406 pages

ISBN:0897918045

DOI:10.1145/237218

Chairman:
Sue Whitesides
McGill Univ.

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 May 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG96

Sponsor:

SoCG96: 12th ACM Symposium on Computational Geometry

May 24 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

SCG '96 Paper Acceptance Rate 48 of 93 submissions, 52%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
378
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Har-Peled SRoy S(2017)Approximating the Maximum Overlap of Polygons under TranslationAlgorithmica10.1007/s00453-016-0152-978:1(147-165)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s00453-016-0152-9
Har-Peled SRoy S(2014)Approximating the Maximum Overlap of Polygons under TranslationAlgorithms - ESA 201410.1007/978-3-662-44777-2_45(542-553)Online publication date: 2014
https://doi.org/10.1007/978-3-662-44777-2_45
Wolovick ND'Argenio PQu H(2009)Optimizing Probabilities of Real-Time Test Case ExecutionProceedings of the 2009 International Conference on Software Testing Verification and Validation10.1109/ICST.2009.59(446-455)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/ICST.2009.59
Ahn HCheong OPark CShin CVigneron A(2007)Maximizing the overlap of two planar convex sets under rigid motionsComputational Geometry: Theory and Applications10.1016/j.comgeo.2006.01.00537:1(3-15)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1016/j.comgeo.2006.01.005
Ahn HBrass PCheong ONa HShin CVigneron A(2006)Inscribing an axially symmetric polygon and other approximation algorithms for planar convex setsComputational Geometry10.1016/j.comgeo.2005.06.00133:3(152-164)Online publication date: Feb-2006
https://doi.org/10.1016/j.comgeo.2005.06.001
Ahn HCheong OPark CShin CVigneron AMitchell JRote G(2005)Maximizing the overlap of two planar convex sets under rigid motionsProceedings of the twenty-first annual symposium on Computational geometry10.1145/1064092.1064146(356-363)Online publication date: 6-Jun-2005
https://dl.acm.org/doi/10.1145/1064092.1064146
de Berg MDevillers Ovan Kreveld MSchwarzkopf OTeillaud M(2005)Computing the maximum overlap of two convex polygons under translationsAlgorithms and Computation10.1007/BFb0009488(126-135)Online publication date: 11-Oct-2005
https://doi.org/10.1007/BFb0009488
Ahn HBrass PCheong ONa HShin CVigneron A(2004)Approximation Algorithms for Inscribing or Circumscribing an Axially Symmetric Polygon to a Convex PolygonComputing and Combinatorics10.1007/978-3-540-27798-9_29(259-267)Online publication date: 2004
https://doi.org/10.1007/978-3-540-27798-9_29

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

Index Terms

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Properties of convex polytopes

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

Abstract

References

Cited By

Index Terms

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Properties of convex polytopes

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations