Home > Research

Possible Future Collaborative Research & Student Projects

Contents:

1. Boundary Conditions of This Work

  1. Use linux when possible, windows when necessary.
  2. 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'
  3. Present results as vividly as possible, with color animations, using the best tools, such as POVRAY. It's ok to use ten times the computing power to present the results as it took to compute them.

2. Current Projects

Here are projects that I am currently interested in.

2.1. Cartography (GIS)

2.1.1. Test Nonphotorealistic Rendering on Terrain

Find or implement an NPR algorithm and test it on terrain.

(undergrad)

Who's doing it: RT.

2.1.2. Overdetermined Laplacian PDE for Terrain Fitting

Experiment with my Matlab program for interpolating from a small set of points to a complete matrix of elevations.

The current status is a Matlab program described in Converting elevation contours to a grid, which was improved by John Child's masters thesis.

For any of the following ideas:

  1. If the input data is larger than about 400x400, first reduce it by either selecting a subset or averaging down.
  2. Try different values of R. Plot the resulting surfaces and show the max and average error.
  3. Try different numbers of points. Plot the error as a function of the number.

Here are some things to try:

  1. Take various sample terrain files, both real USGS data, and generated artificial test data, from my website, delete most of the points, keeping, say, every 5th point in X and Y. Apply overdetsol, and see how good the surface is. Delete more and more points to see how the accuracy degenerates. Plot the resulting accuracy vs number of points.
  2. One of the possible applications is filling in holes in the data. So, take a terrain cell, and delete all the points in, say a circle of diameter 10. Fill in the missing values with overdetsol. Plot the resulting surface; report the error. Vary the '10'.
  3. Take triangle vertices output from TIN, and interpolate them.
  4. For each previous task, plot the error of each post, and look for patterns.
  5. More later...

2.1.3. Hydrological Modeling

2.1.3.1. Survey Existing Work

Test available hydrological modeling (aka water flow, watershed) SW, such as

  1. ArcGIS ARC Hydro
  2. GRASS,
  3. UNC
  4. other major packages?

Use the largest possible datasets.

Write a summary report comparing them on execution time. Compare their output when applied to the same dataset.

2.1.3.2. Implement My Method

Use my Matlab method to determine drainage networks on a large gridded terrain elevation database. Note that detecting and deleting false local minima (traps) is half the total work.

The idea goes as follows.

  1. Initial assumptions:
    1. The input is a matrix of terrain elevations, as from a DEM file.
    2. Assume that each point (post) receives one unit of water.
    3. Assume that all the water falling onto, or flowing into, a point, then flows out to the point's lowest neighbor.
    4. If the point is on the edge and is lower that its 2 or 3 neighbors, then its water flows off the edge of the world.
  2. Processing local catchments:
    1. A major problem is single points, or groups of points, that are lower than their neighbors. Remove them thus:
    2. Make equivalence classes of adjacent cells that are either at the same elevation or within a certain tolerance. This prevents some weird flows within the equal-elevation cells. Note that "within a certain tolerance" is not transitive, but that's probably ok.
    3. Make equivalence classes of local sinks. Note that they may nest.
    4. Subject to some criterion, remove local sinks, by some method.
    5. One easy removal method is to make each sink higher in middle, like inverting it, so water quickly flows off the side. This is good for small or long thin sinks. However, it might create new sinks.
    6. A harder removal method is to fill up sink until it overflows.
  3. Compute the flow:
    1. Form a linear system. The unknown variables are the amount of water flowing out of each point (or equivalence class of points).
    2. Each point induces an equation that says that the water flowing out is the sum of the the water flowing and plus the rain.
    3. Solve it.
  4. Present the results:
    1. Test on the largest possible examples.
    2. Compare the results to other packages.
    3. Make pretty pictures of flows and times.

2.1.3.3. Test the Effect of Lossy Compression and Errors

With both other packages and my method:

  1. Lossily compress and restore the data, and observe the effect on the computed drainage.
  2. Add random noise to the data, and ditto.

(senior - PhD)

2.1.4. Planar Graph Cross Interpolation

My map overlay program 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.

(masters - PhD)

2.1.5. Extend TIN to Insertion and Deletion

My TIN program inserts points into the triangulation. Extend it to also delete points. The process could go as follows.

  1. Estimate an error for each point, P, as follows.
    1. Find the adjacent points to P in the triangulation.
    2. Compute the best fit plane to those points.
    3. Find the distance from P to that plane.
  2. Select the point with smallest error.
  3. Delete the adjacent triangles.
  4. Retriangulate the gap any way. It doesn't matter if the new edges cross outside a concave gap.
  5. Add the new edges, and the old edges around the gap, to the swap queue.
  6. Process the swap queue as when inserting points.

This uses the fact that if the triangulation is "folded over" on itself, say because a concave quadrilateral was split the wrong way, then the diagonal flipping process will fix it. This property is very useful.

2.1.6. Update My TIN Algorithm

Here's a modification that might be faster.

  1. Notes:
    1. We want to handle 75M points.
    2. Inserting points in batches seems potentially faster. However don't insert points that are close to each other in the same iteration, since one point might make the other superfluous.
  2. Triangle data structure:
    1. 3 vertices
    2. name and error of the worst point in it
    3. a status bit telling if this triangle has been selected in step 3 below.
    4. the 1 to 3 adjacent triangles.
    5. plane equation
  3. Steps:
    1. Initially insert 1000 points the old way to create a triangulation.

      Why? It's the only way I know to select good points at the start.

    2. Sort the triangles by max error.
    3. Filter the sorted list in order, selecting triangles to split. Do not select a triangle adjacent to any triangle that is already selected. (I.e., select an "independent" set of triangles.) Stop checking triangles when the max error is less than the desired triangulation tolerance.
    4. Create a new list of vertices from the old vertices plus the worst point in each triangle selected above.
    5. Delete and free the triangle dataset.
    6. Triangulate the point set created above, building a new triangle data structure. Initialize each triangle's worst point to undefined and error to zero.
    7. Process all the non-vertex points:
      1. Determine which triangle contains the point. (See below for how to do this fast.)
      2. Find its error relative to the triangle's plane.
      3. Update the triangle's worst point and max error.
    8. If the worst triangle's error is more than the desired final tolerance, go to step 2.
  4. Batch Point classification: (This takes a triangulation and a set of points, and finds which triangle contains each point.)
    1. Find the set of edges of the triangulation. Each edge has 2 vertices and 2 triangles.
    2. Sort all the points and vertices by X.
    3. Pass thru the list in order. Maintain a list of active edges sorted in Y. The list update event is passing a vertex.
      1. If we pass a vertex, update the sorted active edge list.
      2. Between vertices, sort all the points in Y.
      3. Merge the point list and active edge list.
      4. That classifies each point.
  5. Notes:
    1. The points and vertices need to be sorted only once at the start.
    2. Points become vertices as triangles split, but that doesn't affect the ordering.

2.1.7. 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.

(masters - PhD)

2.1.8. Evaluate Other GIS Packages

Our lab has ESRI Arcview, with several packages, MicroDEM, and Grass. See how well they do, e.g., visibility.

2.1.9. Model-Based Terrain Modelling

Model terrain elevation with a operation like "scooping" instead of, e.g., Fourier series.

(PhD)

2.1.10. Observer Siting, Viewshed, Visibility Index

Extend my observer siting testbed many ways:

Compute changing viewshed as observer moves.

Consider the connectivity of the total visible region.

Consider redundant observers.

Study tradeoff between resolution and time, etc.

Would hierarchical elevation datasets help?

(masters, PhD)

2.2. Computational Geometry

2.2.1. Point Location on Large Planar Graphs

Factor out the point location part of my map overlay area program into a separate program. Test it on large planar graphs (> 100M edges).

Compare to CGAL and any other package that does this.

(senior - masters)

2.2.2. Point Location on Dynamic Planar Graphs

Do point location on large graphs (>>100M edges), whose edges are being inserted and deleted, or are moving.

(masters - PhD)

2.2.3. Point location on billions of VLSI objects

Apply my point location to VLSI databases. Work with a VLSI person.

(masters - PhD)

2.2.4. Planar Graph (Map) Overlay

My map overlay area program computes the area of all the nonempty polygons resulting from overlaying two planar graphs (maps). Extend it to produce the polygons themselves, not just their areas.

(senior - masters)

2.2.5. Compute Percolation With Connected Components

Use my fast connected component program to research percolation.

Robert Sharpley, U South Carolina, at the CARGO kickoff meet, Newport 5/02, knows an application and knows another relevant contact. Ask him. I had dinner with him and Avniel, 5/19/02.

(PhD)

2.2.6. Interference Detection for Moving Objects

Extend my edge intersection algorithm to edges that are being inserted, deleted, and moving. Jeff Trinkle has an application.

2.2.7. Uniting Many Polygons

This is from the DIMACS CGAL workshop 6/02, Minkowski sum talk.

Extend to polygons being inserted, deleted, and moved.

2.2.8. Uniting Many Polyhedra

Extend my mass properties of the union of many cubes thus:

Find the explicit union polyhedron, not just its volume.

Do general polyhedra, not just cubes.

(PhD)

2.2.9. Visible Surface Computation

Reimplement my object-space Visible Surface Algorithm (aka Hidden Surface Algorithm). Test it on the UNC 13M triangle powerplant, and 80M triangle supertanker.

The depth complexity appears to be about 5.

This idea is from my Research Triangle visit 5/02.

(senior - Masters)

2.2.10. Extend Visible Surface Computation to Dynamic Datasets

Handle object-space visibility when polyhedra are being inserted or deleted or are moving.

(PhD)

2.2.11. More Large Spatial Applications

This is open ended.

(PhD)

2.2.12. PCD

I can't remember what PCD means but remember that, at one point, my local topo stuff seemed relevant.

2.3. Computer Assists for Partly-Sighted People

The state of computer HW and SW to assist people with with poor vision is miserable. What there is is poor and/or very expensive. E.g., Screen magnifying SW is several hundred dollars. Possible projects, of varying levels, include the following.

  1. Video magnifier (zoom camera on a stand connecting to monitor) to
    1. read small amount of text, like the return address on letter
    2. see small objects, like the insulin level in needle
    Existing products cost $2000 and up.
  2. Email tool.
  3. Tool to read larger amounts of text, like Kurzweil but cheaper.
  4. Simpler TV remote control, and telephone, with few, large, bright, buttons, and maybe acoustic feedback.
  5. Magnifying pen for single lines of text...
  6. + voice output ...
  7. + haptic feedback to keep user from wandering off the line.

(BS - PhD)

2.4. Automating and Virtualizing GUI Interactions

Abstracting a system to hide its irrelevant complexities, and to provide a base on which to build, has been persistent and successful paradigm throughout Computer Science history. A closely tied concept is the 'filter' to provide properly formatted input to a process, and to convert a process's output into a more useful form. We need to extend abstraction and filtration to systems controlled by graphical user interfaces, jokingly described as WYSIAYG (What You See Is All You Get).

Consider what the transition from textual interfaces to GUIs has cost. If you know the system's next question, you can type ahead, instead of being forced to slow down to the machine's speed. Scripts can be written to control text programs w/o online human input. The output can be analyzed with programs like 'expect', which can then provide appropriate, context sensitive, input. None of this is possible with a graphical interface.

The impact of this defect is more than a matter of speed. A major early Unix philosophy was that multiple text programs can be chained together, so that a complicated task, not envisioned by the original designers, could be solved by connecting several simple standard components. In contrast, just try to connect two interactive forms entry programs.

Our inability to abstract, and build on, graphical interfaces blocks progress by preventing small graphical packages from being put together into one system, and wrapped in a custom interface. What would this allow? At least, one might imagine a GUI wrapper than translated to and from another language, or that made the system accessible to a handicapped person. Currently we are mostly at the mercy of the system designer to provide these capabilities, which means that only large markets get served. The following is an immediate commercial application. The government of the Province of Quebec requires that the SW on business computers generally be in French. Businesses are complaining about the need to buy new SW. Consider the advantage if the currently English graphical SW could be wrapped in a layer that translated to and from French.

This presents both a challenge and an opportunity to IS/IA. The challenge is that easier system connections will facilitate both benevolent and malevolent information flow. It will become easy to wardial GUI systems, searching for vulnerabilities. The opportunity is that GUI systems may be wrapped in interfaces to validate their input, and check that user authorization. Data mining at the union of different systems will be possible. None of this will require any cooperation from the various systems.

(PhD+ level)

3. Inactive Ideas

Here are ideas that, for one reason or another, I'm not actively pursuing. However, they could be activated at some point in the future.

3.1. Cartography

3.1.1. Compression of Correlated Layers

Consider a map with several layers that are related to each other, e.g., elevation, slope, streams, and shorelines. Lossily compress them as a group so that, when restored, they are consistent.

(PhD+ level)

3.2. Misc

3.2.1. Rational Approximations

Investigate rational functions for approximating functions.

(PhD+)

3.2.2. Obsolescence of the Professional Peer-Reviewed Journal Model

There are too many journals, so that important information is spread too thin, and the journals cost too much. Anyone not a member of a cartel (aka major research establishment) cannot afford them. Researchers submit more and more papers and grant proposals, but are less and less willing to review others' submissions. On the other hand, ever better quality information is available, for free, on the web. Even the concept that information consumers would, at least, pay for editors and reviewers to direct them to the worthwhile stuff has not panned out. This can lead to societies who should be concerned with information propagation, ironically being so worried about financial survival that they restrict members' papers' information flow. As members correctly sense the societies' decreasing utility, the societies' membership falls.

What, if anything, should we do about this? Will we all get our information from researchers' own web sites, which we locate with google? How will we then judge their correctness? What happens if spam web pages should arise, in so much greater number than the useful sites, that filtering out the useful sites becomes hard?

The proposed challenge is to devise a new model for the production, vetting, and distribution, of scientific information, and of selecting whom to fund.

(PhD+ level)