tutorial

Progressive Geometric Algorithms

Authors:

M. A. WestenbergAuthors Info & Claims

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

Pages 50 - 59

https://doi.org/10.1145/2582112.2582156

Published: 08 June 2014 Publication History

Get Access

Abstract

Progressive algorithms are algorithms that, on the way to computing a complete solution to the problem at hand, output intermediate solutions that approximate the complete solution increasingly well. We present a framework for analyzing such algorithms, and develop efficient progressive algorithms for two geometric problems: computing the convex hull of a planar point set, and finding popular places in a set of trajectories.

References

[1]

P.K. Agarwal, S. Har-Peled, and K.R. Varadarajan. Geometric approximation via coresets. In Combinatorial and Computational Geometry, volume 52, pages 1--30. Cambridge University Press, 2005.

Google Scholar

[2]

C.B. Barber, D.P. Dobkin, and H. Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. Mathematical Software (TOMS), 22(4):469--483, 1996.

Digital Library

Google Scholar

[3]

M. Benkert, B. Djordjevic, J. Gudmundsson, and T. Wolle. Finding popular places. Internat. J. Comput. Geom. Appl., 20(1):19--42, 2010.

Crossref

Google Scholar

[4]

T.M. Chan. Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. Theory Appl., 35(1):20--35, 2006.

Digital Library

Google Scholar

[5]

P. Diaconis and R.L. Graham. Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society, 39:262--268, 1977.

Google Scholar

[6]

J. Giesen, E. Schuberth, and M. Stojaković. Approximate sorting. Fundamenta Informaticae, 90(1):67--72, 2009.

Digital Library

Google Scholar

[7]

J. Hershberger and S. Suri. Simplified planar coresets for data streams. In Proc. 11th Scandinavian Workshop Algorithm Theory (SWAT), LNCS 5124, pages 5--16, 2008.

Digital Library

Google Scholar

[8]

P. Laube, S. Imfeld, and R Weibel. Discovering relative motion patterns in groups of moving point objects. Internat. J. Geo. Inf. Sci., 19(6):639--668, 2005.

Crossref

Google Scholar

[9]

P. Laube, M. van Kreveld, and S. Imfeld. Finding REMO -- detecting relative motion patterns in geospatial lifelines. In Developments in Spatial Data Handling: Proc. 11th Int. Sympos. Spatial Data Handling, pages 201--215, 2004.

Google Scholar

[10]

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

Digital Library

Google Scholar

[11]

S.J. Russell and S. Zilberstein. Composing real-time systems. In Proc. 12th Int. Joint Conf. on Artificial Intelligence, pages 212--217, 1991.

Digital Library

Google Scholar

[12]

S. Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine, 17:73--83, 1996.

Google Scholar

Cited By

View all

Xiang NWang QYou M(2023)Estimation and update of betweenness centrality with progressive algorithm and shortest paths approximationScientific Reports10.1038/s41598-023-44392-013:1Online publication date: 10-Oct-2023
https://doi.org/10.1038/s41598-023-44392-0
CHIBA KITO H(2022)Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive AlgorithmsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021EAI0003E105.A:3(131-141)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transfun.2021EAI0003
Mesrikhani AFarshi MIranfar B(2020)A Progressive Algorithm for the Closest Pair ProblemInternational Journal of Computer Mathematics: Computer Systems Theory10.1080/23799927.2020.1862302(1-12)Online publication date: 10-Dec-2020
https://doi.org/10.1080/23799927.2020.1862302

Progressive Geometric Algorithms
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Parallel geometric algorithms
Faster geometric algorithms via dynamic determinant computation
ESA'12: Proceedings of the 20th Annual European conference on Algorithms

Determinant computation is the core procedure in many important geometric algorithms, such as convex hull computations and point locations. As the dimension of the computation space grows, a higher percentage of the computation time is consumed by these ...
Sublinear geometric algorithms
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

June 2014

588 pages

ISBN:9781450325943

DOI:10.1145/2582112

Program Chairs:
Siu-Wing Cheng
HKUST
,
Olivier Devillers
INRIA

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 the author(s) 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].

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Tutorial
Research
Refereed limited

Conference

SOCG'14

SOCG'14: Annual Symposium on Computational Geometry

June 8 - 11, 2014

Kyoto, Japan

Acceptance Rates

SOCG'14 Paper Acceptance Rate 60 of 175 submissions, 34%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
199
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xiang NWang QYou M(2023)Estimation and update of betweenness centrality with progressive algorithm and shortest paths approximationScientific Reports10.1038/s41598-023-44392-013:1Online publication date: 10-Oct-2023
https://doi.org/10.1038/s41598-023-44392-0
CHIBA KITO H(2022)Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive AlgorithmsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021EAI0003E105.A:3(131-141)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transfun.2021EAI0003
Mesrikhani AFarshi MIranfar B(2020)A Progressive Algorithm for the Closest Pair ProblemInternational Journal of Computer Mathematics: Computer Systems Theory10.1080/23799927.2020.1862302(1-12)Online publication date: 10-Dec-2020
https://doi.org/10.1080/23799927.2020.1862302
Li RQin LYu JMao RÖzcan FKoutrika GMadden S(2016)Efficient and Progressive Group Steiner Tree SearchProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2915217(91-106)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2915217

View Options

Login options

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

Cited By

Recommendations

Parallel geometric algorithms

Faster geometric algorithms via dynamic determinant computation

Sublinear geometric algorithms