Sampling and sparsification for approximating the packedness of trajectories and detecting gatherings

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F23%3A00553671" target="_blank" >RIV/67985807:_____/23:00553671 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/s41060-021-00301-0" target="_blank" >http://dx.doi.org/10.1007/s41060-021-00301-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s41060-021-00301-0" target="_blank" >10.1007/s41060-021-00301-0</a>

Result language

angličtina

Original language name

Sampling and sparsification for approximating the packedness of trajectories and detecting gatherings

Original language description

Packedness is a measure defined for curves as the ratio of maximum curve length inside any disk divided by its radius. Sparsification allows us to reduce the number of candidate disks for maximum packedness to a polynomial amount in terms of the number of vertices of the polygonal curve. This gives an exact algorithm for computing packedness. We prove that using a fat shape, such as a square, instead of a disk gives a constant factor approximation for packedness. Further sparsification using well-separated pair decomposition improves the time complexity at the cost of losing some accuracy. By adjusting the ratio of the separation factor and the size of the query, we improve the approximation factor of the existing algorithm for packedness using square queries. Our experiments show that uniform sampling works well for finding the average packedness of trajectories with almost constant speed. The empirical results confirm that the sparsification method approximates the maximum packedness for arbitrary polygonal curves. In big data models such as massively parallel computations, both sampling and sparsification are efficient and take a constant number of rounds. Most existing algorithms use line-sweeping which is sequential in nature. Also, we design two data-structures for computing the length of the curve inside a query shape: an exact data-structure for disks called hierarchical aggregated queries and an approximate data-structure for a given set of square queries. Using our modified segment tree, we achieve a near-linear time approximation algorithm.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Structural properties of visibility in terrains and farthest color Voronoi diagrams</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

International Journal of Data Science and Analytics

ISSN

2364-415X

e-ISSN

2364-4168

Volume of the periodical

15

Issue of the periodical within the volume

2

Country of publishing house

CH - SWITZERLAND

Number of pages

16

Pages from-to

201-216

UT code for WoS article

000749228200001

EID of the result in the Scopus database

2-s2.0-85123849200