Kathleen Romanik

Center for Automation Research

University of Maryland

College Park, MD 20742

**Office:** A.V. Williams Building, Room 4469

**Email:**
romanik@cfar.umd.edu

**Phone:** (301) 405-1747

**Fax:** (301) 314-9115

Click here to see photos of my son Ryan!!

Visiting researcher at the Center for Automation Research.

**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

**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

**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

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

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

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

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

Kathleen A. Romanik / romanik@cfar.umd.edu