Open Research Topics

Research archive · original page Research.OpenTopics · last recorded update 2014-01-20

Here are some ideas that I'm pursuing, or would pursue given time. Collaborators and advice are welcome. Good PhD topics are flagged. This page is under construction.

\

Boundary conditions of this work

\

1. Use linux when possible.
2. Use the most powerful tools, such as C++, STL, Boost, Mathematica and Matlab.
3. Document with tools like LaTeX, beamer¹, and a group in my pmwiki wiki.
4. Test everything on the largest, baddest, possible examples. If my algorithm can be broken, I want to know now, not later. Also, my algorithms might perhaps be more robust than others'.
5. Present results as vividly as possible, with color animations, using the best tools, such as POVRAY, Mathematica, VTK, or VISIT. It's ok to use ten times the computing power to present the results as it took to compute them.

\

Useful Themes

\

1. massive databases.
2. massive parallelism.
3. map reduce.
4. dynamic algorithms (i.e., update some property as the data changes).
5. combination of several techniques to increase the power. E.g., suppose that you want terrain compression that preserves legal hydrography. Consider this:
6. Lossily compress while ignoring the hydrography constraint.
7. Then change the restored terrain to make the hydrography legal.

\

Computational cartography

PhD topic

Terrain representation by scooping

The goal is to represent terrain with a set of operators that model, to the appropriate extent, the geophysical processes that created it. This representation would

1. be more compact,
2. facilitate, for the first time, a theoretical analysis of terrain operators like compression and progressive transmission, and
3. allow only legal terrain to be represented.

This, my most powerful long term idea, was the subject of Chris Stuetzle's PhD thesis in July 2012. However, this is a big topic with room for much more research.

undergrad, masters, or PhD topic

Terrain Hydrography Operations

Most terrain is formed by water flowing downhill over the surface. This induces many interesting problems. E.g., Tsz-Yam Eddie Lau's expected PhD thesis in Dec 2012 will study completing fragmentary drainage patterns. Here are several possible future projects.

First, define hydrographicly valid terrain to be terrain with no interior local minima (aka pits, depressions, or basins).

1. Lossily compress terrain while preserving hydrographic validity as follows.
2. Lossily compress terrain w/o attempting to preserve hydrographic validity.
3. Restore the terrain per the compression algorithm.
4. Then perturb the restored terrain to be hydrographicly valid. The obvious method is simply to fill in the basins.
5. Current hydrographic (river) computation algorithms often have all the water that flows out of a pixel flow to the lowest neighbor. While this is obvious, it can lead to multiple parallel long thin watersheds. That is not realistic. This idea is to modify the Dijkstra shortest path algorithm so that the water leaving a pixel may not flow to the lowest neighbor, if that leads to a better river lower down. Investigate this to see if more realistic watersheds are generated.
6. Modify the hydrographic computation so that a given fraction of the water entering a pixel does not flow out (but rather sinks in or is evaporated). This will allow computation of the absolute, rather than merely the relative, amount of water flowing through each pixel. That is useful for flood determination.
7. Extend Eddie Lau's work for terrain compression that starts with computing the hydrography, then compressing it, and inferring the terrain from it.

PhD topic

Compressing 4- and 5- dimensional data with ODETLAP

\ ODETLAP has proven very effective at compressing \(E^2\) terrain. Extend it to compressing medical or geological data in \(E^4\).

1. With \(E^2\) ODETLAP, there is an equation for every interior point, setting it to the average of its 4 neighbors in the grid.
2. With \(E^4\) ODETLAP, there is an equation for every interior point, setting it to the average of its 8 neighbors in the volume.
3. In either case, border points are a separate issue.
4. Try to ignore them for now.
5. Otherwise, set each border point to the average of all of its legal neighbors, those that are not outside the universe.
6. However, that biasses the slope of the surface towards horizontal at the edge.
7. In either case, each known point has an additional equation setting it equal to its known value.
8. This produces a sparse overdetermined system.
9. The question in higher dimensions is, how fast can this be solved? That depends on how much the sparse matrix fills in as variables are eliminated.
10. Fills in means that some zero entries become nonzero. That is undesirable since it costs time and space.

You Li's PhD started researching this. Dan Beneditti is continuing. However, there is a lot more to be done.

PhD topic

Slope compression with ODETLAP

Xie and Tracy have extended ODETLAP to compress terrain so that the reconstructed terrain has accurate slope. The idea is to add new equations to encourage the reconstructed surface's slope to be close to the original surface's slope.

It may take some thinking to realize how major this is. We are not representing slope explicitly in the compressed surface. Rather, we are lossily compressing the surface so that its computed slope is reasonable accurate. SFAIK no one is doing compression like that.

The more general problem is compressing correlated layers of data while keeping them consistent with each other. Consistency is more important than accuracy.

Extend this work.

PhD topic

ODETLAP with Other PDEs

Our current version of ODETLAP uses the Laplacian (heat flow) PDE, possibly extended for slopes. Investigate other PDEs such as the thin plate equation. Note that the slope compression described above is one such extension.

It now appears that the thin-plate PDE is no better than the Laplacian, so this theme is (for now) suspended.

PhD topic

Multiobserver Siting

1. Investigate the effect of compression and of errors on the quality of the multi-observer siting.
2. Concerning 'quality', I don't care whether the observers moved, provided that they are just as effective in their new locations. That is a more sophisticated and realistic metric than other people may be using. It is also more difficult to understand. :-(
3. I showed many years ago that viewshed computations have a large error bar. A minor change in interpolating terrain height between adjacent posts in the Lake Champlain West DEM changed the visibility of half of all the targets in the DEM. That apparent problem is really an opportunity. It means that faster algorithms might produce equally good results. Investigate this idea.
4. Visibility has recently come to the attention of several other researchers. I am not interested in an incremental research here, but in something transformational. E.g.,
5. How can we use visibility to represent terrain?
6. Can we combine visibility with hydrography?

undergrad or masters topic

NPR terrain rendering

Test Non Photorealistic Rendering of terrain - does it bring out the details?

undergrad, masters, or PhD topic

Map overlay

Overprop, My map overlay area calculation program takes two maps (aka planar graphs), A and B, covering the same region. Then it computes the areas of all the nonempty intersections between any polygon of A with any polygon of B. It is very fast, and operates in time linear in the size of the input and output. Several open problems arise.

1. This can easily be extended to interpolate data from one map to another. E.g., we could estimate the population of drainage polygons by how much they overlap the census polygons, whose populations we know. However this assumes that the population in each census polygon is even across the whole census polygon, and then jumps discontinuously at the border. Generalize the interpolation to assume the population is varying smoothly. That is, the census polygons are sampling a smooth population distribution. Resample it into drainage polygons. This idea is from Fred Broome.
2. Test Overprop on much larger datasets.
3. Overprop is very parallelizable. Implement and test this.
4. I have an implementation using rational numbers. There is no unexpected roundoff error, but the program is slower. Extend this.
5. Extend to a general overlay program. The newly available large datasets make this more interesting.

masters, or PhD topic

TIN with Curved Patches

Extend the TIN to use triangular splines of higher degree, instead of triangular planar patches. The first step is to compute the curved patches for an existing TIN, then see if the fit is improved. If so, then this tells us something about the surface's continuity.

However, there may be technical reasons why this is hard.

\ \

Computational geometry - specific

undergrad, masters, or PhD topic

Applications of connected components

I have a very fast implementation of a union-find connected component algorithm, that runs on a \(20\,000\times20\,000\) bitmap in \(E^2\) or \(1000\times1000\times1000\) bitmap in \(E^3\). The input is an array of bits, or voxels that have been classified, in \(E^3\); the output a list of the connected components together with their volumes and surface areas. This is a solution waiting for a problem.

1. One possible application would be to extend it to compute porosity of a material like soil. My program would compute the region(s) connecting the top and bottom of the soil sample. The research would start with computing the conductivity of such irregularly shaped regions.
2. My program facilitates experiments on random connectivity, that is connectivity, fractal dimension, etc, of volumes where each voxel is randomly empty or solid. Take this idea somewhere.
3. Compare this to Streaming Connected Component Computation for Trillion Voxel Images, Martin Isenburg and Jonathan Shewchuk, at the Workshop on Massive Data Algorithmics, June 11, 2009.

undergrad or masters topic

Nearest neighbors

I have a very fast nearest neighbor query program. It preprocesses N fixed points in \(E^3\). Perhaps \( N>10^8 \). Then, given a query point, it quickly finds the closest fixed point. Here are some resulting open problems.

1. ANN (Approximate NN) is a widely used nearest neighbor program. I think we can beat ANN; they disagree that I've shown that. Demonstrating this needs more work. My advantages are:
2. Simple compact data structure allows large datasets to be processed internally.
3. Constant preprocessing and query time per point — no \(\log N\)) factors. For large \(N\), that's significant.
4. The fast preprocessing time facilitates dynamic 'fixed' point sets. That is, if the 'fixed' points are moving, it may be easier for us to update the data structure or even to recompute it from scratch.
5. My data structure might be more tolerant of very unevenly spaced data, such as data that is locally 2-D, perhaps derived from a laser range scanner. However, this needs to be demonstrated. The project here is to run experiments and collect data to see whether I am right. Beating a widely used method would be fun. ANN was reporting an erroneously large query time because of an overflow, so we're currently not faster than it for queries. We are faster and smaller for the preprocessing. We might have other advantages, but this is lower priority for the moment.
6. Extend my program to
7. Find the K nearest neighbors.
8. Find all neighbors within a given distance of the query.
9. Find all pairs of points that are closer than a given distance.
10. Do an approximate query. 'Approximate' may have various meanings. Perhaps it's ok to return a point not more than a certain distance farther than the closest point.

PhD topic

Local topological data structures

1. A local data structure for a polygon or polyhedron represents that object with a set of primitives that depend on only local properties of each vertex.
2. No global info such, as complete edges, is explicit, altho it may be derived if necessary.
3. Many properties, such as volume and surface area, and operations, may be computed with a reduction operation on that set.
4. The idea may be extended to computing the volume of the union of polyhedra.
5. An advantage of this method is that most of its steps are reduction operations that may be parallelized.

The goal here is to extend this idea. It is fun to go in the opposite direction from the widely held belief that we should use lots of global topology.

IMHO, this research direction is greatly underappreciated. It is very useful in, e.g., distributed computing.

Unifying example - Volume of union of many polyhedra

Several of the ideas described here fit together nicely, e.g., in the application of computing mass properties of boolean combinations many polyhedra. I've an algorithm and implementation for theh volume of the union of many cubes, tested to \(2\cdot 10^7\) cubes. The theoretical analysis, substantiated by experimental measurements, is that the time is linear in the number of cubes.

This is another solution looking for a problem. This is also extremely parallelizable. My latest implementation, using OpenMP, runs 10x faster on 32 threads than on one thread.

How would it work on CUDA?

Can we extend from volume of union to the union itself?

A theme would be to make this dynamic.

Computational geometry - general

Turn static geometry algorithms into dynamic

Examples include nearest points and mass properties of the union of multiple polyhedra. My simpler data structures, such as the uniform grid, are more amenable to this than some competing ones.

Internal algorithms

1. Most researchers do not exploit the large amounts of cheap RAM now available.
2. For several years, I've had a machine with 64GB of main memory. I'm considering a machine with 192GB.
3. Do something good with this.

External algorithms

1. What big datasets are big enough? Clearly some datasets will be that large. However, with a compact representation, we can do a lot more internally than people realize. That means that when we do go external, the appropriate algorithm and data structure might be different.
2. E.g., I originally designed my connected component algorithm to be efficient when external. However, even when processing more than \(10^9\) binary voxels, that wasn't necessary.
3. One technique might be to add a new level to the uniform grid.
4. The quasi-linear properties of external media have perhaps not been properly exploited. On the one hand, sequential reads are much faster than randomly seeking to another position in the file. On the other hand, large blocks can often be transposed in constant time merely by swapping pointers.

PhD topic

Parallel

1. I graduated 2 PhDs in parallel Computational Geometry in the 1980s, but then switched back to using serial machines. Now it's time to return to this, using my new machine with a K20x NVidia compute processor.
2. Many of my algorithms can be cast in the mapcar aka map-reduce aka scatter-gather paridigm that is recently popular with Google. E.g., consider the steps of the uniform grid for edge segment intersection:
3. For each edge segment, determine what cells it passes thru.
4. Invert that relation so that we know the segments contained in each cell.
5. For each cell, intersect all pairs of segments in that cell.

Steps 1 and 3 are totally parallelizable. Simple data structures really pay off here.

Identifying complete neurons from images.

One problem is to determine the neurons or blood vessels from a confocal microscope image. The image shows many disconnected pieces; the task is to connect them in a logical pattern.

My ideas is to impose structure on the space between object such as neuron parts, in order to fill in gaps. This is analogous to filling in drainage patterns in cartography.

This topic would require a professional collabator who knows the subject.

Protein docking

Given two molecules, do an unconstrained optimization using the 6-12 law. This is an obvious idea that no one appears to be doing. Therefore it probably has a fatal flaw. That might be that it gets hung up in local optima or else it is too slow.

Or, it might be that no one has has used a good optimization algorithm that uses the 2nd derivative (Jacobian) of the objective function. Our objective function has an easy 2nd derivative, but optimization implementations that can use it are hard to find.

One possible solution to the local optima hang-up might be to start with thousands of random initial positions. That works if the process if fast enough.

The purpose of this exercise is to investigate this idea.

It's not clear that this topic needs more research. The existing techniques might be good enough.

Notes

1. Many topics mentioned on this page, such as this one, have useful wikipedia entries