Article

Free access

Efficient approximation and optimization algorithms for computational metrology

Authors:

Christian A. Duncan,

Michael T. Goodrich,

Edgar A. RamosAuthors Info & Claims

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

Pages 121 - 130

Published: 05 January 1997 Publication History

PDF eReader

References

[1]

P. K. AGARWAL, B. ARONOV, AND M. SHARIR, Computing envelopes in four dimensions with applications, in Proc. 10th Annu. ACM Sympos. Comput. Geom., 1994, pp. 348-358.

Digital Library

Google Scholar

[2]

P. K. AGARWAL, J. J, MATOUSEK, AND S. SURI, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Comput. Geom. Theory Appl., I (1992), pp. 189-201.

Digital Library

Google Scholar

[3]

P. K. AGARWAL AND M. SHARIR, Off-line dynamic maintenance of the width of a planar point set, Comput. Geom. Theory Appl., I (1991), pp. 65-78.

Digital Library

Google Scholar

[4]

~, Planar geometric location problems and maintaining the width of a planar set, Algorithmica, 11 (1994), pp. 185-195.

Google Scholar

[5]

, Efficient randomized algorithms for some geometric optimization problems, in Proc. 11th Annu. ACM Sympos. Comput. Geom., 1995, pp. 326-335.

Digital Library

Google Scholar

[6]

P. $. AGARWAL, M. SHARIR, AND S. TOLEDO, Applications of parametric searching in geometric optimization, J. Algorithms, 17 (1994), pp. 292-318.

Digital Library

Google Scholar

[7]

S. ARYA, D. M. MOUNT, N. S. NETANYAHU, R. SILVERMAN, AND A. Wu, An optimal algorithm for approximate nearest neighbor searching, in Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, 1994, pp. 573-582.

Digital Library

Google Scholar

[8]

B. CHAZELLE, An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom., 10 (1993), pp. 377-409.

Google Scholar

[9]

B. CHAZELLE, H. EDELSBRUNNER, L. GUIBAS, AND M. SHARIR: Diameter, width, closest line pair and parametric searching, Discrete Comput. Geom., 10 (1993), pp. 183~196.

Google Scholar

[10]

K. L. CLARKSON, Linear programming in O(n3d2) time, Inform. Process. Lett., 22 (1986), pp. 21-24.

Digital Library

Google Scholar

[11]

~, ALas Vegas algorithm for linear programming when the dimension is small, in Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., 1988, pp. 452-456.

Google Scholar

[12]

R. COLE, Slowing down sorting networks to obtain 208.

Digital Library

Google Scholar

[13]

M. B. DILLENCOURT, D. M. MOUNT, AND N. S. NET- ANYAHU, A randomized algorithm for slope selection, Internat. J. Comput. Geom. Appl., 2 (1992), pp. 1-27.

Google Scholar

[14]

W. P. DONG, E. MAINSAH, P. F. SULLIVAN, AND K. F. STOUT, Instruments and measurement techniques of 3-dimensional surface topography, in Three- Dimensional Surface Topography: Measurement, Interpretation and Applications, K. F. Stout, ed., Penton Press, Bristol, Penn., 1994.

Google Scholar

[15]

M. E. DYBR, On a multidimensional search technique and its application to the Euclidean one-center problem, SIAM J. Comput., 15 (1986), pp. 725-738.

Digital Library

Google Scholar

[16]

H. EBARA, N. FUKUYAMA, H. NAKANO, AND Y. NA- KANISHI, Roundness algorithms using the Voronoi diagrams, in Abstracts 1st Caned. Conf. Comput. Geom., 1989, p. 41.

Google Scholar

[17]

H. EDELSBRUNNER, Algorithms in Combinatorial Geometry, vol. 10 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Heidelberg, West Germany, 1987.

Digital Library

Google Scholar

[18]

S. FORTUNE AND C. J. VAN WYK, Efficient exact arithmetic for computational geometry, in Proc. 9th Annu. ACM Sympos. Comput. Geom., 1993, pp. 163- 172.

Digital Library

Google Scholar

[19]

M. E. HOULE AND G. T. TOUSSAINT, Computing the width of a set, in Proc. 1st Annu. ACM Sympos. Comput. Geom., 1985, pp. 1-7.

Digital Library

Google Scholar

[20]

, Computing the width of a set, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-10 (1988), pp. 761- 765.

Digital Library

Google Scholar

[21]

R. JANAROAN, On maintaining the width and diameter of a planar point-set online, Internat. J. Comput. Geom. Appl., 3 (1993), pp. 331-344.

Google Scholar

[22]

V. B. LE AND D. T. LEE, Out-of-roundness problem revisited, IEEE Trans. Pattern Anal. Mech. Intell., PAMI-13 (1991), pp. 217-223.

Digital Library

Google Scholar

[23]

J. M^TOU~EK, Randomized optimal algorithm for slope selection, Inform. Process. Lett., 39 (1991), pp. 183- 187.

Digital Library

Google Scholar

[24]

P. MCMULLEN, The maximal number/of faces of a convex polytope, Mathematica, 17 (1970), pp. 179-184.

Google Scholar

[25]

N. MEGIDDO, Applying parallel computation algorithms in the design of serial algorithms, J. ACM, 30 (1983), pp. 852-865.

Digital Library

Google Scholar

[26]

~, Linear-time algorithms }or linear programming in Ra and related problems, SIAM J. Comput., 12 (1983), pp. 759-776.

Google Scholar

[27]

, Linear programming in linear time when the dimension is fixed, J. ACM, 31 (1984), pp. 114-127.

Digital Library

Google Scholar

[28]

F. P. PaEPARATX AND M. I. SHAMOS, Computational Geometry: An Introduction, Springer-Verlag, New York, NY, 1985.

Digital Library

Google Scholar

[29]

A. A. G. REQUICHA, Mathematical meaning and computational representation of tolerance specifications, in Proc. 1993 Int. Forum on Dimensional Tolerancing and Metrology, 1993, pp. 61-68.

Google Scholar

[30]

G. ROTE, C. SCHWARZ, AND J. SNOEYINK, Maintaining the approximate width of a set of points in the plane, in Proc. 5th Caned. Conf. Comput. Geom., Waterloo, Canada, 1993, pp. 258-263.

Google Scholar

[31]

R. SEIDEL, Small-dimensional linear programming and convex hulls made easy, Discrete Comput. Geom., 6 (1991), pp. 423-434.

Crossref

Google Scholar

[32]

L. SHAPER AND W. STEIGER, Randomizi?~g optimal geometric algorithms, Technical Report 94-22, DIMACS, 1995.

Google Scholar

[33]

T. C. SHERMER AND C. K. YAP, Probing for nearcenters and estimating relative roundness, in Proc. ASME Workshop on Tolerancing and Metrology, 1995.

Google Scholar

[34]

J. R. SUEWCHUK, Robust adaptive floating-point geometric predicates, in Proc. 12th Annu. ACM Sympos. Comput. Geom., 1996, pp. 141-150.

Digital Library

Google Scholar

[35]

M. SMID AND R. J ANARDAN, On the width and roundness of a set of points in the plane, in Proc. 7th Caned. Conf. Comput. Geom., 1995, pp. 193-198.

Google Scholar

[36]

V. SRINIVASAN, Role of sweeps in tolerance semantics, in Proc. 1993 Int. Forum on Dimensional Tolerancing and Metrology, 1993, pp. 69-78.

Google Scholar

[37]

K. SWANSON, D. T. LEE, AND V. L. Wu, An optimal algorithm for roundness determination on convex polygons, Computational Geometry: Theory and Applications, 5 (1995), pp. 225-235.

Digital Library

Google Scholar

[38]

R. K. WALKER AND V. SRINIVASAN, Creation and evolution of the ASME YIj.5.1M standard, in Proc. 1993 Int. Forum on Dimensional Tolerancing and Metrology, 1993, pp. 19-30.

Google Scholar

[39]

C. K. YAP, Towards exact geometric computation, in Proc. 5th Canadian Conference on Computational Geometry (CCCG), 1993, pp. 405-419.

Google Scholar

[40]

~, Exact computational geometry and tolerancing metrology, in Snapshots of Computational and Discrete Geometry, Vol. 3, Tech. Rep. SOCS-94.50, D. Avis and J. Bose, eds., McGill School of Comp. Sci., 1995.

Google Scholar

Cited By

View all

Nievergelt Y(2013)Fitting cylinders to dataJournal of Computational and Applied Mathematics10.5555/2397198.2397254239(250-269)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.5555/2397198.2397254
Mukherjee JSinha Mahapatra PKarmakar ADas S(2013)Minimum-width rectangular annulusTheoretical Computer Science10.1016/j.tcs.2012.02.041508(74-80)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.02.041
Mukherjee JMahapatra PKarmakar ADas S(2011)Minimum width rectangular annulusProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021951(364-374)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021951
Show More Cited By

Index Terms

Efficient approximation and optimization algorithms for computational metrology

Recommendations

Genetic algorithms for modelling and optimisation
Special issue: Mathematics applied to immunology

Genetic algorithms (GAs) are a heuristic search and optimisation technique inspired by natural evolution. They have been successfully applied to a wide range of real-world problems of significant complexity. This paper is intended as an introduction to ...
Bacterial foraging optimisation algorithm, particle swarm optimisation and genetic algorithm: a comparative study

Nature inspired meta-heuristic algorithms have been widely used in order to find efficient solutions for optimisation problems, and granted results have been achieved. Particle swarm optimisation PSO algorithm is one of the most utilised algorithms in ...
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

January 1997

788 pages

ISBN:0898713900

Chairman:
Michael Saks

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 1997

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
470
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)8

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nievergelt Y(2013)Fitting cylinders to dataJournal of Computational and Applied Mathematics10.5555/2397198.2397254239(250-269)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.5555/2397198.2397254
Mukherjee JSinha Mahapatra PKarmakar ADas S(2013)Minimum-width rectangular annulusTheoretical Computer Science10.1016/j.tcs.2012.02.041508(74-80)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.02.041
Mukherjee JMahapatra PKarmakar ADas S(2011)Minimum width rectangular annulusProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021951(364-374)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021951
Lee D(2010)Computational geometry IIAlgorithms and theory of computation handbook10.5555/1882723.1882725(2-2)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882725
Chan T(2009)Dynamic CoresetsDiscrete & Computational Geometry10.5555/3116272.311651442:3(469-488)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.5555/3116272.3116514
Koltun VSharir M(2009)On Overlays and Minimization DiagramsDiscrete & Computational Geometry10.5555/3115960.311606041:3(385-397)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.5555/3115960.3116060
Chan TTeillaud M(2008)Dynamic coresetsProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377680(1-9)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377680
Chan T(2006)Faster core-set constructions and data-stream algorithms in fixed dimensionsComputational Geometry: Theory and Applications10.5555/1646483.164657835:1-2(20-35)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.5555/1646483.1646578
Koltun VSharir MAmenta NCheong O(2006)On overlays and minimization diagramsProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137914(395-401)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137914
Agarwal PProcopiuc CVaradarajan K(2005)Approximation Algorithms for a k-Line CenterAlgorithmica10.1007/s00453-005-1166-x42:3-4(221-230)Online publication date: 1-Jul-2005
https://dl.acm.org/doi/10.1007/s00453-005-1166-x
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

Index Terms

Recommendations

Genetic algorithms for modelling and optimisation

Bacterial foraging optimisation algorithm, particle swarm optimisation and genetic algorithm: a comparative study

Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems