Article

Free access

Parallel robust algorithms for constructing strongly convex hulls

Authors:

Wei Chen,

Koichi Wada,

Kimio KawaguchiAuthors Info & Claims

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

Pages 133 - 140

https://doi.org/10.1145/237218.237329

Published: 01 May 1996 Publication History

PDF eReader

References

[1]

A. Aggarwal, B. Chazelle, L. Glfibas, C. O'Dunlaing, and C. Yap: Parallel computational geometry. Alqorithmica. 3, 293-327, 1988.

Digital Library

Google Scholar

[2]

D. Dobkin and D. Silver: R,ecipcs for geometry and numerical analysis~-part I: An empirical study. In Proc. of the jr h, Annual A CM Symposium on Computational Geometry, 93-105, 1988.

Digital Library

Google Scholar

[3]

S. Fortune: Stable maintenance of point set trianglllations in two dimensions. In Proc. of the 30th Annual Symposium on Foundations of Computer Science, 494-499, 1989.

Digital Library

Google Scholar

[4]

A. Gibbons and W. R.ytter: Efficient parallel algorithms. Cambrid. qe University Press, 1988.

Digital Library

Google Scholar

[5]

D. H. Greene and F. F. Yao: Finite-resolution comp~tational geometry. In Proc. of the 27th IEEE Symposium on Foundations of Computer Science, 143-152, 1986.

Digital Library

Google Scholar

[6]

L. Gllibas, D Salesin and J. Stolfi: Epsilon geometry: building algorithms from imprecise computations. In Proc. of the 5th Annual A 6',M ~?}rn, pos'iurn, on Computational Georo, ctry, 208-217, 1989.

Digital Library

Google Scholar

[7]

L. Guibas, D Salesin and J. Stolfi: Constmlcting strongly convex approximate hulls with inaccllrate primitives. Algorithmica, 9, 534- 560, 1993.

Crossref

Google Scholar

[8]

C. Hoffman: The problem of acc,lracy and robustness in geometric computation. Computer, 22, 31-42, 1989.

Digital Library

Google Scholar

[9]

Z. Li and V. J. Milenkovic: Constructing strongly convex hulls using exact or rounded arithmetic. Algorithmica, vol. 8, 345-364, 1992.

Digital Library

Google Scholar

[10]

V. J. Milcnkovic: Verifiable implementations of geometric algorithms ~sing finite precision arithmetic. Artificial Intelligence, 37, 377- 401, 1988.

Digital Library

Google Scholar

[11]

V. J. Milenkovic: Calculating approximate curve arrangements using rounded arithmetic. In Proc. the 5th Annual A CAlf Symposium on Computational Geometry, 197-207, 1989.

Digital Library

Google Scholar

[12]

V. J. Milcnkovic: Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic. In Proc. of the 30th Annual $ymposiurn on Foundations of Computer Science, 500-505, 1989.

Digital Library

Google Scholar

[13]

T. Ottmann, F. Thiemt and C. Ullrich: Numerical stability of geometric algorithms. In, Proc. the 3th Annual A CM Symposiurn on Computational Geometry, 119-125, 1987.

Digital Library

Google Scholar

Cited By

View all

CHEN WDENG XWADA KKAWAGUCHI K(2011)CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTSInternational Journal of Computational Geometry & Applications10.1142/S021819590100061411:05(487-502)Online publication date: 20-Nov-2011
https://doi.org/10.1142/S0218195901000614
Chen WDeng XWada KKawaguchi K(2006)Constructing a strongly convex superhull of pointsComputing and Combinatorics10.1007/BFb0045071(42-51)Online publication date: 24-Jan-2006
https://doi.org/10.1007/BFb0045071
Schirra S(2005)Precision and robustness in geometric computationsAlgorithmic Foundations of Geographic Information Systems10.1007/3-540-63818-0_9(255-287)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-63818-0_9

Index Terms

Parallel robust algorithms for constructing strongly convex hulls
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel algorithms
2. Theory of computation

Recommendations

Robust algorithms for constructing strongly convex hulls in parallel

Given a set S of n points in the plane, an ε-strongly convex δ-hull of S is defined as a convex polygon P with the vertices taken from S such that no point of S lies farther than δ outside P and such that even if the vertices of P are perturbed by as ...
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 ...
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^@__ __), ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

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

3
Total Citations
View Citations
514
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)3

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

CHEN WDENG XWADA KKAWAGUCHI K(2011)CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTSInternational Journal of Computational Geometry & Applications10.1142/S021819590100061411:05(487-502)Online publication date: 20-Nov-2011
https://doi.org/10.1142/S0218195901000614
Chen WDeng XWada KKawaguchi K(2006)Constructing a strongly convex superhull of pointsComputing and Combinatorics10.1007/BFb0045071(42-51)Online publication date: 24-Jan-2006
https://doi.org/10.1007/BFb0045071
Schirra S(2005)Precision and robustness in geometric computationsAlgorithmic Foundations of Geographic Information Systems10.1007/3-540-63818-0_9(255-287)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-63818-0_9

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

Robust algorithms for constructing strongly convex hulls in parallel

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

Convex hulls of spheres and convex hulls of disjoint convex polytopes