### Abstract

We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon P with n vertices in a read only memory, and additional working memory of size m, the new algorithm computes the shortest path (in P) in O(n2/m) expected time, assuming m = O(n/ log^{2} n). This requires several new tools, which we believe to be of independent interest. Specifically, we show that violator space problems, an abstraction of low dimensional linearprogramming (and LP-type problems), can be solved using constant space and expected linear time, by modifying Seidel s linear programming algorithm and using pseudo-random sequences.

Original language | English (US) |
---|---|

Title of host publication | 31st International Symposium on Computational Geometry, SoCG 2015 |

Editors | Janos Pach, Janos Pach, Lars Arge |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 111-125 |

Number of pages | 15 |

ISBN (Electronic) | 9783939897835 |

DOIs | |

State | Published - Jun 1 2015 |

Event | 31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands Duration: Jun 22 2015 → Jun 25 2015 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 34 |

ISSN (Print) | 1868-8969 |

### Other

Other | 31st International Symposium on Computational Geometry, SoCG 2015 |
---|---|

Country | Netherlands |

City | Eindhoven |

Period | 6/22/15 → 6/25/15 |

### Fingerprint

### Keywords

- Limited space
- Shortest path
- Violator spaces

### ASJC Scopus subject areas

- Software

### Cite this

*31st International Symposium on Computational Geometry, SoCG 2015*(pp. 111-125). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 34). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SOCG.2015.111