 | |
A bounding-volume hierarchy is a tree structure on a set of geometric
objects (the data objects). Each object is stored in a leaf of the tree.
Each internal node stores for each of its children u an additional
geometric object V(u), that encloses all data objects that are
stored in descendants of u (a minimum bounding rectangle, for example).
In other words, V(u) is a
bounding volume for the descendants of u. Bounding-volume hierarchies
can be used to do many types of queries on the set of data objects.
For example, all data objects that intersect a query window Q can
be found by recursively visiting all nodes whose bounding volumes
intersect Q. For an more elaborate introduction to bounding volume hierarchies
I put a small excerpt from my PhD thesis on-line.
We do theoretical and experimental research into the construction of bounding-volume
hierarchies such as R-trees and similar data structures with good query times.
We have been exploring two approaches to build bounding-volume hiearchies: approaches
based on binary space partitions (BSP's), and approaches based on space-filling curves.
The most comprehensive and general treatment of the BSP-based approach in two
dimensions is in our paper
Efficient c-oriented range searching with DOP-trees.
A three-dimensional variant is discussed in
Box-trees for collision checking in industrial installations.
External-memory variants are discussed in
The Priority R-Tree.
The approach based on space-filling curves seems to be more practical and is discussed in detail
in our most recent papers.
Papers:
- Four-dimensional Hilbert curves for R-trees (2009)
- Locality and bounding-box quality of two-dimensional space-filling curves (2008, 2009)
- Space-filling curve properties for efficient spatial index structures (2008)
- I/O-efficient map overlay and point location in low-density subdivisions (2007)
- Efficient c-oriented range searching with DOP-trees (2005, 2009)
- Cache-oblivious R-trees (2005, 2009)
- The Priority R-Tree: a practically efficient and worst-case-optimal R-tree (2004, 2008)
- Box-trees for collision checking in industrial installation (2002, 2004)
- Box-trees and R-trees with near-optimal query time (2001, 2002)
For more information, see Publications. |
|
Currently working with:
Mark de Berg
Joery Mens
Elena Mumford
Shripad Thite
Laura Toma
Freek van WalderveenOther co-authors:
Pankaj Agarwal
Lars Arge
Joachim Gudmundsson
Mikael Hammar
Micha Streppel
Ke Yi |
|
Geographic information systems form a continuing source of inspiration for
research questions, ranging from small-scale geometric problems to the issues
of computations on massive data sets that do not fit in main memory. Papers:
- Improved visibility computation on massive grid terrains (2009)
- Simple I/O-efficient flow accumulation on grid terrains (2009)
- Visibility maps of realistic terrains have linear smoothed complexity (2009)
- The complexity of flow on fat terrains and its I/O-efficient computation (2007, 2009)
- Computing visibility on terrains in external memory (2007, 2009)
- Algorithmic aspects of proportional symbol maps (2006, 2009)
- River networks and watershed maps of triangulated terrains revisited (2006)
- I/O-efficient hierarchical watershed decomposition of grid terrain models (2005, 2006)
- Constrained higher-order delaunay triangulations (2003, 2005)
- Finding a minimal tree in a polygon with its medial axis (1999)
For more information, see Publications. |
|
Currently working with:
Mark de Berg
Jeremy Fishman
Jeffrey Janssen
Laura Toma
Constantinos TsirogiannisOther co-authors:
Lars Arge
Hans Bodlaender
Sergio Cabello
Otfried Cheong
Andrew Danner
Joachim Gudmundsson
Jung-Gun Lim
Marc van Kreveld
Bettina Speckmann
Norbert Zeh
Yi Zhuang |
|
In a geometric network, the nodes and connections are geometric objects.
Almost invariably, the purpose of the network is to provide connections between
the nodes in the network: the connections have to span the network.
Often it is desirable that the connection through the network between
any pair of nodes is relatively
short. From this viewpoint, one would ideally have a direct connection
between any pair of nodes. This is usually infeasible due to the costs
involved, so one has to compromise between the quality and the cost of
the connections. This leads to optimization problems of the following form:
find the "best" set of connections for a given set of geometric objects,
subject to a given set of constraints. Papers:
- Computing a minimum-dilation spanning tree is NP-hard (2007, 2008)
- Sparse geometric graphs with small dilation (2005, 2008)
- Constructing interference-minimal networks (2005, 2006)
- Optimal spanners for axis-aligned rectangles (2004, 2005)
- Facility location and the geometric minimum-diameter spanning tree (2002, 2004)
For more information, see Publications. |
|
Currently working with:
Peter Kooijmans
Bettina Speckmann
Marco VerstegeOther co-authors:
Boris Aronov
Tetsuo Asano
Marc Benkert
Mark de Berg
Otfried Cheong
Hazel Everett
Joachim Gudmundsson
Naoki Katoh
Mira Lee
Sang-Min Park
Chan-Su Shin
Michiel Smid
Antoine Vigneron
Alexander Wolff |
| Boundary labelling |
|
Co-authors: |
2006-2008
In figures in books, on screen etc. there are often points that need to be
labelled. It is not always possible to place the labels close to the points.
A reasonable alternative is to place the labels next to the actual illustration and
connect each point to its label by a curve. To do this, we have to decide
where exactly to place each point's label and how to draw the curves such
that the connections between points and labels are clear and the curves do
not clutter the figure. This leads to optimisation problems such as how to
match label positions on the boundary of the figure with points in the figure,
such that we can connect them by non-intersecting curves of a certain type
and the curves have minimum total length or minimum total number of bends.Papers:
- Algorithms for multi-criteria one-sided boundary labeling (2007)
For more information, see Publications. |
|
Marc Benkert
Moritz Kroll
Martin Nöllenburg |
| |
