Code for the Papers
Practical Insertion-Only Convex Hull
@inbook{doi:10.1137/1.9781611978957.6,
author = {Ivor van der Hoog and Henrik Reinstädtler and Eva Rotenberg},
title = {Practical Insertion-Only Convex Hull},
booktitle = {2026 Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)},
chapter = {},
pages = {71-84},
doi = {10.1137/1.9781611978957.6},
URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611978957.6},
eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611978957.6},
abstract = { Convex hull data structures are fundamental in computational geometry. We study insertiononly data structures for convex hulls of a planar point set \(P\) of size \(n\), supporting various containment and intersection queries. When \(P\) is sorted by \(x\)- or \(y\)-coordinate, convex hulls can be constructed in linear time using classical algorithms such as Graham scan. In the fully dynamic setting, the algorithm by Overmars and van Leeuwen [35] maintains the convex hull under insertions and deletions in \(O(\text{log}^2 n)\) time per update, supports queries in time logarithmic in the size of the convex hull, and uses \(O(n)\) space. An open-source implementation of their method is available. We investigate a variety of methods tailored to the insertion-only setting. We explore a broad selection of trade-offs involving robustness, memory access patterns, and space usage, providing an extensive evaluation of both existing and novel techniques. We observe that all logarithmic-time methods rely on pointer-based tree structures, which suffer in practice due to poor memory locality. Motivated by this, we develop a vector-based solution inspired by Overmars’ logarithmic method [34]. Our structure has worse asymptotic bounds, supporting queries in \(O(\text{log}^2 n)\) time, but stores data in \(O(\text{log}\, n)\) contiguous vectors, greatly improving cache performance. Through empirical evaluation on real-world and synthetic data sets, we uncover surprising trends. Let \(h\) denote the size of the convex hull. We show that a naïve \(O(h)\) insertion-only algorithm based on Graham scan consistently outperforms both theoretical and practical state-of-the-art methods under realistic workloads, even on data sets with rather large convex hulls. While tree-based methods with \(O(\text{log}\, h)\) update times offer solid theoretical guarantees, they are never optimal in practice. In contrast, our vector-based logarithmic method, despite its theoretically inferior bounds, is highly competitive across all tested scenarios. It is optimal whenever the convex hull becomes large. This paper has been awarded the “Code and Data Available” and “Results Reproduced” badges as recognition that the author(s) have followed reproducibility principles. Code and data that allow readers to reproduce the results in this paper are available at https://zenodo.org/records/17338250. Participation in the ALENEX artifact evaluation phase was optional and performed at the request of the author(s). }
}
by Ivor van der Hoog, Henrik Reinstädtler and Eva Rotenberg published in ALENEX'26.
and
Engineering Fully Dynamic Convex Hulls
by Ivor van der Hoog, Henrik Reinstädtler and Eva Rotenberg to be published in SEA'26.
The most up-to-date code for this project can be found at github.com/henrixapp/PracticalConvexHulles .
You can find the experiment configs for the alenex paper in the directory experiments/alenex26 and for the SEA paper in experiments/sea26. Instructions on how to run can be found below.
You can find the data for this paper in the following sources:
- The mammals collection https://figshare.com/articles/dataset/pone_d_15_41735data_tar_bz2/2372716?file=4012228 In the
animalsdirectory. Please concatenate all sub files in each directory into ainstance.txt - TIGER set can be found at Zenodo
- Clustering set can be found at https://cs.joensuu.fi/sipu/datasets/
Dependencies: Please use git submodule init && git submodule update to get Gaede et als. implementation and the btree implementation.
Have gcc>=12 installed and use bazel 8.0 (to install we would recommend https://github.com/bazelbuild/bazelisk/releases install by placing the bazelisk executable in a location of your path as bazel file)
Compile:
bazel build -c opt app # -c dbg for debugging symbols.
When using the sources from zenodo you can add --vendor_dir=vendor_src to use the vendored dependencies to build the project offline.
./bazel-bin/app/app --command_textproto 'command:"run" instance {name:"bell:1048576:box:1048576:6:1000" query_type:"bbox" insert_type:"circle" insertion_count:1048576 query_count: 1048576 deletion_count:0 seed:3 double_params{key:"radius" value:1000} } config { algorithm_configs{data_structure:"in_memory_queries" algorithm_name:"bucket_512"} }'
Valid query_type/insert types:
boxbelldiskcircle
Use the radius to change the radius/length of the boxes.
Set insertion/query count to any number you wish. If mix is set to true, the insertions and queries will be randomly shuffled.
The setting for deletions deletion_count can only be greater 0 for fully dynamic algorithms.
If mix_deletions: true, the deletions are mixed as well.
You can also specify parts in the instance to simulate multiple phases (see experiments/sea/sequences).
Valid algorithm_names (instead of _bucket_512):
avl_treeImplements a graham scan on an AVL-Tree with balancing operations. Can be appended with:exactfor exact calculation.vector_grahamImplements a linear search, graham scan on a vector. Get exact kernel by appending:exactbtree\_{16,256,1024,4096}runs using a btree with the given size in bytes per node (exact available for final config usingbtree_1024:exact)cgalruns the cgal implementation at the end once (at the first query), is not a dynamic algorithm. Use only for comparisonnaiveinserts at the end, resorts and does a grahamscan.terribleruns at terrible floating point algorithm( calculating the x-axis and using division).bucket\_{8,64,512,4096}Runs our new algorithm with a first bucket size of either 8, 64, 512 or 4096. Suffixes::btreeuses a btree as first bucket.:real_sizecreates a new bucket only if the hull has reached the first bucket size:exactfor 512 variant and after:btreeor:real_size: Calculate using CGALs exact kernel.
dpch_dynamicthe fully dynamic code by Shirgure.{cq,ch}_tree{:inexact}runs the fully dynamic algorithm CH or CQ-Tree by Gaede et al. Use:inexactto use inexact calculations else it will use CGALs Exact_predicates_inexact_constructions_kernel .btree_naiveThe Naive fully dynamic semi-static algorithm from the SEA'26 paper.dynamic_he_{1024,32}The dynamic algorithm FDH from our SEA'26 paper with first bucket size 1024 or 32.
You can use the data_structure circle_box_on_the_fly to use an on the fly generator instead of in_memory_queries.
Compile using
bazel build -c opt runner:fork_runner
and run on an experiment.textproto in a folder (experiment_path without experiment.textproto!)
./bazel-bin/runner/fork_runner --experiment_path /path/to/folder/containing/experiment.textproto --random_order 1 --max_alloc_memory <max memory in MB used by runner> --max_alloc_memory_per_process <max memory per experiment> --cycles_to_queue_new 1 --seed 1234
Please install texlive (xelatex) from a different source (your os), to allow the compilation.
Run
bazel run -c opt tools/plot:plot_cc -- /absolute/path/to/containing/experiments /absolute/path/to/vis.textproto
This should generate a folder vis in /absolute/path/to/containing/experiments