Interactive Exploration of the Temporal $\alpha$-Shape

Felix Weitbrecht

arxiv: 2303.00878 · v3 · pith:YPT56B7Mnew · submitted 2023-03-02 · 💻 cs.CG

Interactive Exploration of the Temporal α-Shape

Felix Weitbrecht This is my paper

Pith reviewed 2026-05-24 10:07 UTC · model grok-4.3

classification 💻 cs.CG

keywords temporal alpha-shapealpha-shapesDelaunay triangulationtime-window queriesinteractive visualizationcomputational geometryoutput-sensitive algorithms

0 comments

The pith

The temporal α-shape encodes every possible α-shape across all time windows and can be built in output-sensitive linear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to build a single compact structure, called the temporal α-shape α_T, that contains every α-shape that could arise for any choice of time window and any α-value. Once α_T exists, any requested α-shape for a user-chosen interval can be read off directly instead of being recomputed from the raw points. The construction runs in time linear in the size of α_T itself and rests on a prior routine that enumerates all Delaunay triangles over every time window in constant time per triangle. Experiments indicate the resulting description stays modest in size and yields at least a 52-fold speedup over recomputing shapes on demand. The same linear-time guarantee holds in any fixed dimension.

Core claim

The temporal α-shape α_T is a minimal description of all α-shapes over all time windows and can be computed in output-sensitive linear time from the set of all Delaunay triangles over all time windows, which are themselves obtainable in constant time per triangle by an existing algorithm. Complexity bounds on the size of α_T are provided, and the structure supports immediate extraction of any requested α-shape for an arbitrary time window without further geometric computation.

What carries the argument

The temporal α-shape α_T, a single compact object that stores every α-shape that can arise for any time window.

If this is right

Any α-shape for an arbitrary time window and α-value can be reported in time proportional only to its own size.
Interactive visualization tools can respond to changes in the selected time window without restarting the geometric computation.
The same linear-time guarantee extends directly to point sets in any fixed dimension d.
The size of α_T admits explicit upper and lower bounds in terms of the number of distinct Delaunay triangles over time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same compact-representation idea could be applied to other time-varying geometric structures such as convex layers or minimum spanning trees.
If the underlying point set is itself generated by a continuous motion model, α_T might be maintained dynamically under insertions and deletions of points.
The output-sensitive linear bound suggests that α_T could serve as a canonical index for any temporal point-set query that ultimately depends on Delaunay information.

Load-bearing premise

An algorithm already exists that can list every Delaunay triangle that appears in any time window in constant time per triangle.

What would settle it

A family of point sets in the plane for which the number of distinct Delaunay triangles across all time windows is linear in the input size yet the size of α_T grows super-linearly in that number, or the construction time exceeds linear in |α_T|.

Figures

Figures reproduced from arXiv: 2303.00878 by Felix Weitbrecht.

read the original abstract

Shape is a powerful tool to understand point sets. A formal notion of shape is given by $\alpha$-shapes, which generalize the convex hull and provide adjustable level of detail. Many real-world point sets have an inherent temporal property as natural processes often happen over time, like lightning strikes during thunderstorms or moving animal swarms. To explore such point sets, where each point is associated with one timestamp, interactive applications may utilize $\alpha$-shapes and allow the user to specify different time windows and $\alpha$-values. We show how to compute the temporal $\alpha$-shape $\alpha_T$, a minimal description of all $\alpha$-shapes over all time windows, in output-sensitive linear time. We also give complexity bounds on $|\alpha_T|$. We use $\alpha_T$ to interactively visualize $\alpha$-shapes of user-specified time windows without having to constantly compute requested $\alpha$-shapes. Experimental results suggest that our approach outperforms an existing approach by a factor of at least $\sim$52 and that the description we compute has reasonable size in practice. The basis for our algorithm is an existing algorithm which computes all Delaunay triangles over all time windows using $\mathcal{O}(1)$ time per triangle. Our approach generalizes to higher dimensions with the same runtime for fixed $d$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines a temporal α-shape α_T as a compact summary of all α-shapes across time windows and claims an output-sensitive linear-time construction, but the runtime argument rests on an unproven step that avoids paying for the full set of temporal Delaunay triangles.

read the letter

The core contribution is the α_T structure itself: a single precomputed object that encodes every possible α-shape for every time window without recomputing from scratch each time. That matches the interactive use case they describe, and the reported 52× speedup over a baseline that recomputes on the fly is the kind of practical gain that matters for visualization tools. They also give bounds on the size of α_T and note that the construction generalizes to fixed dimension d with the same asymptotic cost. Those pieces are concrete and directly tied to the stated goal of supporting user-specified windows and α values on timestamped point sets like animal tracks or lightning data. The experimental claim that the description stays reasonable in practice is useful even if the data sets are not fully detailed in the abstract. The soft spot is the runtime claim. The method is said to rest on an existing linear-time-per-triangle enumeration of all temporal Delaunay triangles. If the number of those triangles is asymptotically larger than |α_T|, then any approach that materializes or iterates over the full set will take Ω(D) time rather than O(|α_T|). The abstract does not spell out an additional filtering step that would keep the total cost linear in the output size, nor does it include a proof sketch. Without that argument the output-sensitive guarantee is not yet established. The paper is aimed at computational geometers who already work with α-shapes or kinetic data structures and who need fast interactive queries on temporal point sets. A reader already familiar with the cited temporal Delaunay result will be able to judge whether the new extraction step closes the gap. It is worth sending to referees because the application is clear, the experimental numbers are reported, and the central idea is a natural extension rather than a reinvention; the theory section will need the missing argument but the work is grounded enough to merit review.

Referee Report

1 major / 0 minor

Summary. The manuscript introduces the temporal α-shape α_T as a minimal description of all α-shapes over all time windows for temporally annotated point sets. It claims an algorithm to compute α_T in output-sensitive linear time O(|α_T|), provides complexity bounds on |α_T|, enables interactive visualization of user-specified time windows and α-values without repeated computation, reports experimental speedups of ~52×, and states that the approach generalizes to higher dimensions with the same runtime for fixed d. The method builds on a cited prior algorithm that enumerates all Delaunay triangles over all time windows in O(1) time per triangle.

Significance. If the central runtime claim holds with a rigorous proof, the result would support efficient interactive exploration of temporal point sets using α-shapes, with applications in domains involving time-stamped data such as environmental monitoring or animal tracking. The output-sensitive nature, complexity bounds, and reported practical performance are strengths; the generalization to fixed d is also positive. The work explicitly builds on an independent prior result rather than deriving runtime from fitted parameters.

major comments (1)

[Abstract] Abstract: The claim that α_T can be computed in output-sensitive linear time O(|α_T|) is presented as following directly from the cited prior algorithm that enumerates all Delaunay triangles over time windows in O(1) time per triangle. However, if the total number of such triangles D satisfies D = ω(|α_T|), any approach that materializes or iterates over the full Delaunay set would require Ω(D) time, contradicting the O(|α_T|) bound unless an additional filtering or implicit representation step proven to run in O(|α_T|) time is described. No such step or proof sketch is indicated in the abstract, making the central claim load-bearing and unsubstantiated based on the provided information.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and the constructive comment on the abstract. We address the point below and indicate the planned revision.

read point-by-point responses

Referee: [Abstract] Abstract: The claim that α_T can be computed in output-sensitive linear time O(|α_T|) is presented as following directly from the cited prior algorithm that enumerates all Delaunay triangles over time windows in O(1) time per triangle. However, if the total number of such triangles D satisfies D = ω(|α_T|), any approach that materializes or iterates over the full Delaunay set would require Ω(D) time, contradicting the O(|α_T|) bound unless an additional filtering or implicit representation step proven to run in O(|α_T|) time is described. No such step or proof sketch is indicated in the abstract, making the central claim load-bearing and unsubstantiated based on the provided information.

Authors: We agree that the abstract does not explicitly describe the additional mechanism that yields the O(|α_T|) bound. The full manuscript explains that the algorithm processes the output of the cited prior work via an output-sensitive filtering procedure that builds α_T incrementally and discards non-contributing Delaunay triangles without materializing the full set D; the filtering is proven to run in O(|α_T|) time. To address the referee's observation, we will revise the abstract to include a concise reference to this filtering step and its complexity. This change makes the claim self-contained in the abstract while preserving the manuscript's technical content. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithm builds on independent prior Delaunay result

full rationale

The paper's derivation claims output-sensitive linear time for α_T by building directly on an existing (external) algorithm that enumerates all Delaunay triangles in O(1) time per triangle. The abstract explicitly positions this prior algorithm as the basis, with the new contribution being extraction of the minimal α_T description. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the same authors, or ansatzes smuggled via citation appear. The runtime claim is asserted relative to the prior per-triangle cost and output size |α_T|, without reducing the result to its own inputs by construction. This is the normal case of a paper extending an independent cited subroutine.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the definition of α_T as a minimal covering structure and on the runtime guarantee of the cited base Delaunay algorithm; no free parameters or invented physical entities appear.

axioms (1)

domain assumption An existing algorithm computes every Delaunay triangle over all time windows in O(1) time per triangle.
Explicitly invoked in the abstract as the foundation of the new linear-time method.

invented entities (1)

temporal α-shape α_T no independent evidence
purpose: Minimal description containing every α-shape for every time window
Newly introduced combinatorial structure whose size and construction are the main objects of study.

pith-pipeline@v0.9.0 · 5748 in / 1288 out tokens · 47774 ms · 2026-05-24T10:07:10.782061+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Spatio-temporal shape from silhouette using four-dimensional Delaunay meshing

Ehsan Aganj, Jean-Philippe Pons, Florent S \'e gonne, and Renaud Keriven. Spatio-temporal shape from silhouette using four-dimensional Delaunay meshing. In 2007 IEEE 11th International Conference on Computer Vision , pages 1--8. IEEE, 2007. https://doi.org/10.1109/ICCV.2007.4409016 doi:10.1109/ICCV.2007.4409016

work page doi:10.1109/iccv.2007.4409016 2007
[2]

Box-trees and r-trees with near-optimal query time

Pankaj Agarwal, Mark de Berg, Joachim Gudmundsson, Mikael Hammar, and Herman Haverkort. Box-trees and r-trees with near-optimal query time. Discrete & Computational Geometry , 28:291--312, 2001. https://doi.org/10.1007/s00454-002-2817-1 doi:10.1007/s00454-002-2817-1

work page doi:10.1007/s00454-002-2817-1 2001
[3]

Retrieving  -shapes and schematic polygonal approximations for sets of points within queried temporal ranges

Annika Bonerath, Benjamin Niedermann, and Jan - Henrik Haunert. Retrieving  -shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems , pages 249--258. ACM , 2019. https://doi.org/10.1145/3347146.335...

work page doi:10.1145/3347146.3359087 2019
[4]

Juri Buchmüller, Dominik Jäckle, Eren Cakmak, Ulrik Brandes, and Daniel A. Keim. Motionrugs: Visualizing collective trends in space and time. IEEE Transactions on Visualization and Computer Graphics , 25(1):76--86, 2019. https://doi.org/10.1109/TVCG.2018.2865049 doi:10.1109/TVCG.2018.2865049

work page doi:10.1109/tvcg.2018.2865049 2019
[5]

Orthogonal point location and rectangle stabbing queries in 3-d

Timothy Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. Orthogonal point location and rectangle stabbing queries in 3-d. Journal of Computational Geometry , 13(1):399--428, 2022. https://doi.org/10.20382/jocg.v13i1a15 doi:10.20382/jocg.v13i1a15

work page doi:10.20382/jocg.v13i1a15 2022
[6]

Department of Commerce DOC/NOAA/NESDIS/NCDC > National Climatic Data Center, NESDIS

NOAA U.S. Department of Commerce DOC/NOAA/NESDIS/NCDC > National Climatic Data Center, NESDIS. Storm events data, 1950 -- present. URL: https://www.ncei.noaa.gov/access/metadata/landing-page/bin/iso?id=gov.noaa.ncdc:C00510

work page 1950
[7]

Alpha shapes-a survey

Herbert Edelsbrunner. Alpha shapes-a survey. In Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings . 2011

work page 2011
[8]

Kirkpatrick, and Raimund Seidel

Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Transactions on Information Theory , 29(4):551--559, 1983. https://doi.org/10.1109/TIT.1983.1056714 doi:10.1109/TIT.1983.1056714

work page doi:10.1109/tit.1983.1056714 1983
[9]

Three-dimensional alpha shapes

Herbert Edelsbrunner and Ernst P M \"u cke. Three-dimensional alpha shapes. ACM Transactions on Graphics (TOG) , 13(1):43--72, 1994. https://doi.org/10.1145/174462.156635 doi:10.1145/174462.156635

work page doi:10.1145/174462.156635 1994
[10]

Efficiently computing all Delaunay triangles occurring over all contiguous subsequences

Stefan Funke and Felix Weitbrecht. Efficiently computing all Delaunay triangles occurring over all contiguous subsequences. In 31st International Symposium on Algorithms and Computation (ISAAC 2020) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.ISAAC.2020.28 doi:10.4230/LIPIcs.ISAAC.2020.28

work page doi:10.4230/lipics.isaac.2020.28 2020
[11]

Guibas, Donald E

Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica , 7(1):381--413, 1992. https://doi.org/10.1007/BF01758770 doi:10.1007/BF01758770

work page doi:10.1007/bf01758770 1992
[12]

: High-resolution volumetric computation of offset surfaces with feature preservation

Jochen S \"u muth, Marco Winter, and G \"u nther Greiner. Reconstructing animated meshes from time-varying point clouds. In Computer Graphics Forum , volume 27, pages 1469--1476. Wiley Online Library, 2008. https://doi.org/10.1111/j.1467-8659.2008.01287.x doi:10.1111/j.1467-8659.2008.01287.x

work page doi:10.1111/j.1467-8659.2008.01287.x 2008
[13]

Identification of scandinavian commercial species of individual trees from airborne laser scanning data using alpha shape metrics

Jari Vauhkonen, Timo Tokola, Petteri Packal \'e n, and Matti Maltamo. Identification of scandinavian commercial species of individual trees from airborne laser scanning data using alpha shape metrics. Forest Science , 55(1):37--47, 2009. https://doi.org/10.1093/forestscience/55.1.37 doi:10.1093/forestscience/55.1.37

work page doi:10.1093/forestscience/55.1.37 2009
[14]

Linear time point location in Delaunay simplex enumeration over all contiguous subsequences

Felix Weitbrecht. Linear time point location in Delaunay simplex enumeration over all contiguous subsequences. In EuroCG , pages 399--404, 2022. URL: http://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf

work page 2022
[15]

DelaunayEnumerator, a GitHub repository

Felix Weitbrecht. DelaunayEnumerator, a GitHub repository . https://github.com/felixweitbrecht/DelaunayEnumerator, 2023

work page 2023
[16]

On the number of Delaunay simplices over all time window in any dimension

Felix Weitbrecht. On the number of Delaunay simplices over all time window in any dimension. In EuroCG , pages 39--45, 2023. URL: https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/05/Booklet_EuroCG2023.pdf

work page 2023

[1] [1]

Spatio-temporal shape from silhouette using four-dimensional Delaunay meshing

Ehsan Aganj, Jean-Philippe Pons, Florent S \'e gonne, and Renaud Keriven. Spatio-temporal shape from silhouette using four-dimensional Delaunay meshing. In 2007 IEEE 11th International Conference on Computer Vision , pages 1--8. IEEE, 2007. https://doi.org/10.1109/ICCV.2007.4409016 doi:10.1109/ICCV.2007.4409016

work page doi:10.1109/iccv.2007.4409016 2007

[2] [2]

Box-trees and r-trees with near-optimal query time

Pankaj Agarwal, Mark de Berg, Joachim Gudmundsson, Mikael Hammar, and Herman Haverkort. Box-trees and r-trees with near-optimal query time. Discrete & Computational Geometry , 28:291--312, 2001. https://doi.org/10.1007/s00454-002-2817-1 doi:10.1007/s00454-002-2817-1

work page doi:10.1007/s00454-002-2817-1 2001

[3] [3]

Retrieving \( \) -shapes and schematic polygonal approximations for sets of points within queried temporal ranges

Annika Bonerath, Benjamin Niedermann, and Jan - Henrik Haunert. Retrieving \( \) -shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems , pages 249--258. ACM , 2019. https://doi.org/10.1145/3347146.335...

work page doi:10.1145/3347146.3359087 2019

[4] [4]

Juri Buchmüller, Dominik Jäckle, Eren Cakmak, Ulrik Brandes, and Daniel A. Keim. Motionrugs: Visualizing collective trends in space and time. IEEE Transactions on Visualization and Computer Graphics , 25(1):76--86, 2019. https://doi.org/10.1109/TVCG.2018.2865049 doi:10.1109/TVCG.2018.2865049

work page doi:10.1109/tvcg.2018.2865049 2019

[5] [5]

Orthogonal point location and rectangle stabbing queries in 3-d

Timothy Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. Orthogonal point location and rectangle stabbing queries in 3-d. Journal of Computational Geometry , 13(1):399--428, 2022. https://doi.org/10.20382/jocg.v13i1a15 doi:10.20382/jocg.v13i1a15

work page doi:10.20382/jocg.v13i1a15 2022

[6] [6]

Department of Commerce DOC/NOAA/NESDIS/NCDC > National Climatic Data Center, NESDIS

NOAA U.S. Department of Commerce DOC/NOAA/NESDIS/NCDC > National Climatic Data Center, NESDIS. Storm events data, 1950 -- present. URL: https://www.ncei.noaa.gov/access/metadata/landing-page/bin/iso?id=gov.noaa.ncdc:C00510

work page 1950

[7] [7]

Alpha shapes-a survey

Herbert Edelsbrunner. Alpha shapes-a survey. In Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings . 2011

work page 2011

[8] [8]

Kirkpatrick, and Raimund Seidel

Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Transactions on Information Theory , 29(4):551--559, 1983. https://doi.org/10.1109/TIT.1983.1056714 doi:10.1109/TIT.1983.1056714

work page doi:10.1109/tit.1983.1056714 1983

[9] [9]

Three-dimensional alpha shapes

Herbert Edelsbrunner and Ernst P M \"u cke. Three-dimensional alpha shapes. ACM Transactions on Graphics (TOG) , 13(1):43--72, 1994. https://doi.org/10.1145/174462.156635 doi:10.1145/174462.156635

work page doi:10.1145/174462.156635 1994

[10] [10]

Efficiently computing all Delaunay triangles occurring over all contiguous subsequences

Stefan Funke and Felix Weitbrecht. Efficiently computing all Delaunay triangles occurring over all contiguous subsequences. In 31st International Symposium on Algorithms and Computation (ISAAC 2020) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.ISAAC.2020.28 doi:10.4230/LIPIcs.ISAAC.2020.28

work page doi:10.4230/lipics.isaac.2020.28 2020

[11] [11]

Guibas, Donald E

Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica , 7(1):381--413, 1992. https://doi.org/10.1007/BF01758770 doi:10.1007/BF01758770

work page doi:10.1007/bf01758770 1992

[12] [12]

: High-resolution volumetric computation of offset surfaces with feature preservation

Jochen S \"u muth, Marco Winter, and G \"u nther Greiner. Reconstructing animated meshes from time-varying point clouds. In Computer Graphics Forum , volume 27, pages 1469--1476. Wiley Online Library, 2008. https://doi.org/10.1111/j.1467-8659.2008.01287.x doi:10.1111/j.1467-8659.2008.01287.x

work page doi:10.1111/j.1467-8659.2008.01287.x 2008

[13] [13]

Identification of scandinavian commercial species of individual trees from airborne laser scanning data using alpha shape metrics

Jari Vauhkonen, Timo Tokola, Petteri Packal \'e n, and Matti Maltamo. Identification of scandinavian commercial species of individual trees from airborne laser scanning data using alpha shape metrics. Forest Science , 55(1):37--47, 2009. https://doi.org/10.1093/forestscience/55.1.37 doi:10.1093/forestscience/55.1.37

work page doi:10.1093/forestscience/55.1.37 2009

[14] [14]

Linear time point location in Delaunay simplex enumeration over all contiguous subsequences

Felix Weitbrecht. Linear time point location in Delaunay simplex enumeration over all contiguous subsequences. In EuroCG , pages 399--404, 2022. URL: http://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf

work page 2022

[15] [15]

DelaunayEnumerator, a GitHub repository

Felix Weitbrecht. DelaunayEnumerator, a GitHub repository . https://github.com/felixweitbrecht/DelaunayEnumerator, 2023

work page 2023

[16] [16]

On the number of Delaunay simplices over all time window in any dimension

Felix Weitbrecht. On the number of Delaunay simplices over all time window in any dimension. In EuroCG , pages 39--45, 2023. URL: https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/05/Booklet_EuroCG2023.pdf

work page 2023