### Abstract

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distancefrom x to any other point in P is minimized, where the link distance between two points x, y inside P isdefined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We proveseveral geometric properties of the link center and present an algorithm that calculates this set in time0(n^{2}), where n is the number of sides of P. We also give an 0 (n log n) algorithm for finding apoint x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.

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

Title of host publication | Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 |

Editors | D. Soule |

Publisher | Association for Computing Machinery, Inc |

Pages | 1-10 |

Number of pages | 10 |

ISBN (Electronic) | 0897912314, 9780897912310 |

DOIs | |

State | Published - Oct 1 1987 |

Event | 3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada Duration: Jun 8 1987 → Jun 10 1987 |

### Publication series

Name | Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 |
---|

### Other

Other | 3rd Annual Symposium on Computational Geometry, SCG 1987 |
---|---|

Country | Canada |

City | Waterloo |

Period | 6/8/87 → 6/10/87 |

### ASJC Scopus subject areas

- Computational Mathematics
- Geometry and Topology

## Fingerprint Dive into the research topics of 'Computing the link center of a simple polygon'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987*(pp. 1-10). (Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987). Association for Computing Machinery, Inc. https://doi.org/10.1145/41958.41959