Progressive geometric algorithms

S.P.A. Alewijnse; T.M. Bagautdinov; M.T. Berg, de; Q.W. Bouts; A.P. Brink, ten; K. Buchin; M.A. Westenberg

doi:10.1145/2582112.2582156

Progressive geometric algorithms

S.P.A. Alewijnse, T.M. Bagautdinov, M.T. Berg, de, Q.W. Bouts, A.P. Brink, ten, K. Buchin, M.A. Westenberg

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

197 Downloads (Pure)

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.

Original language	English
Title of host publication	30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014)
Place of Publication	New York
Publisher	Association for Computing Machinery, Inc
Pages	50-59
ISBN (Print)	978-1-4503-2594-3
DOIs	https://doi.org/10.1145/2582112.2582156
Publication status	Published - 2014
Event	30th Annual Symposium on Computational Geometry (SoCG 2014) - Kyoto, Japan Duration: 8 Jun 2014 → 11 Jun 2014 Conference number: 30

Conference

Conference	30th Annual Symposium on Computational Geometry (SoCG 2014)
Abbreviated title	SoCG '14
Country/Territory	Japan
City	Kyoto
Period	8/06/14 → 11/06/14

Access to Document

10.1145/2582112.2582156

progressive-geometric-authorfinalFinal author version , 407 KB

Cite this

@inproceedings{4952a869287d448cbc1d5632f322d048,

title = "Progressive geometric algorithms",

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.",

author = "S.P.A. Alewijnse and T.M. Bagautdinov and {Berg, de}, M.T. and Q.W. Bouts and {Brink, ten}, A.P. and K. Buchin and M.A. Westenberg",

year = "2014",

doi = "10.1145/2582112.2582156",

language = "English",

isbn = "978-1-4503-2594-3",

pages = "50--59",

booktitle = "30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "30th Annual Symposium on Computational Geometry (SoCG 2014), SoCG '14 ; Conference date: 08-06-2014 Through 11-06-2014",

}

Alewijnse, SPA, Bagautdinov, TM, Berg, de, MT, Bouts, QW, Brink, ten, AP, Buchin, K & Westenberg, MA 2014, Progressive geometric algorithms. in 30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014). Association for Computing Machinery, Inc, New York, pp. 50-59, 30th Annual Symposium on Computational Geometry (SoCG 2014), Kyoto, Japan, 8/06/14. https://doi.org/10.1145/2582112.2582156

TY - GEN

T1 - Progressive geometric algorithms

AU - Alewijnse, S.P.A.

AU - Bagautdinov, T.M.

AU - Berg, de, M.T.

AU - Bouts, Q.W.

AU - Brink, ten, A.P.

AU - Buchin, K.

AU - Westenberg, M.A.

N1 - Conference code: 30

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1145/2582112.2582156

DO - 10.1145/2582112.2582156

M3 - Conference contribution

SN - 978-1-4503-2594-3

SP - 50

EP - 59

BT - 30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014)

PB - Association for Computing Machinery, Inc

CY - New York

T2 - 30th Annual Symposium on Computational Geometry (SoCG 2014)

Y2 - 8 June 2014 through 11 June 2014

ER -

Progressive geometric algorithms

Abstract

Conference

Access to Document

Fingerprint

Cite this