Kathleen A. Romanik

Visiting researcher at the Center for Automation Research.

Research interests:

Personal:

• Curriculum Vitae
• Resumé(Postscript)
• Research Interests

Publications:

Robot Localization

• Localizing a Robot with Minimum Travel
  SIAM Journal on Computing - to appear

  We consider the problem of localizing a robot in a known environment. We assume that the robot has a map and a compass and can ``see'' walls using a range sensing device. By moving around and using range sensing, the robot can determine possibilities for its position in the map. The goal is to minimize the distance that the robot travels in order to exactly identify its position. We show that the localization problem is NP-hard, and we develop a polynomial time approximation scheme that travels close to the optimal distance.
  

  Preview PostScript

Software Testing

• Using Vapnik Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments
  Information and Computation - to appear

  We examine the complexity of testing different control flow statements of standard programming languages by defining a complexity measure that is similar to the Vapnik-Chervonenkis dimension used in computational learning theory and applying it to different control flow statements and combinations of statements. This measure gives bounds on the number of random test points needed to determine that a program is approximately correct, and thus it gives insight into the relative difficulty of testing different program constructions.
  

  Preview PostScript

Graph Drawing

• On a Visibility Representation for Graphs in Three Dimensions
  McGill University School of Computer Science
  Technical Report TR-SOCS-94.50, July 1994

  We study a 3-dimensional visibility representation for graphs that maps vertices to closed, axis-parallel rectangles and expresses edges by vertical visibility between rectangles. We examine which kinds of graphs are representable in this way.
  

  Preview PostScript

• Directed VR-Representable Graphs Have Unbounded Dimension
  Graph Drawing '94, Princeton NJ, October 1994, pp. 177-181
  
  

  Preview PostScript

• Directed Rectangle-Visibility Graphs Have Unbounded Dimension
  DIMACS Technical Report 95-7, April 1995
  
  

  Preview PostScript

Geometric Probing

• Geometric Probing and Testing - A Survey
  DIMACS Technical Report 95-42, September 1995
  
  

  Preview PostScript

• Testing Simple Polygons
  Computational Geometry: Theory and Applications - to appear
  
  

  Preview PostScript

• Testing Orthogonal Shapes
  Computational Geometry: Theory and Applications 5 (1995) 33-49
  
  

  Preview PostScript