Otfried Schwarzkopf

SODA Conference 2004 Conference Paper

On finding a guard that sees most and a shop that sells most

• Otfried Schwarzkopf
• Alon Efrat
• Sariel Har-Peled

TCS Journal 1995 Journal Article

Reaching a goal with directional uncertainty

• Mark de Berg
• Leonidas Guibas
• Dan Halperin
• Mark Overmars
• Otfried Schwarzkopf
• Micha Sharir
• Monique Teillaud

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region R α(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of R α(S) is O( n α5 ). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k 3 m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

STOC Conference 1994 Conference Paper

On lazy randomized incremental construction

• Mark de Berg
• Katrin Dobrindt
• Otfried Schwarzkopf

STOC Conference 1993 Conference Paper

A deterministic algorithm for the three-dimensional diameter problem

• Jirí Matousek 0001
• Otfried Schwarzkopf

STOC Conference 1993 Conference Paper

Piecewise linear paths among convex obstacles

• Mark de Berg
• Jirí Matousek 0001
• Otfried Schwarzkopf

FOCS Conference 1991 Conference Paper

Dynamic Maintenance of Geometric Structures Made Easy

• Otfried Schwarzkopf

The problem of dynamically maintaining geometric structures is considered. A technique is proposed that uses randomized incremental algorithms which are augmented to allow deletions of objects. A model for distributions on the possible input sequences of insertions and deletions is developed and analyzed using R. Seidel's backwards analysis. It is further shown how to apply this to maintain Voronoi diagrams, convex hulls, and planar subdivisions. A strikingly simple algorithm for the maintenance of convex hulls in any dimension is given. The expected running time is determined. >