Inducing polygons of line arrangements
| Autor: | Mumford, E., Scharf, L., Scherfenberg, M., Petitjean, S. |
|---|---|
| Přispěvatelé: | Algorithms |
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: | |
| Zdroj: | Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008), 107-110 STARTPAGE=107;ENDPAGE=110;TITLE=Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008) |
| Popis: | We show that an arrangement A of n lines in general position in the plane has an inducing polygon of size O(n). Additionally, we present a simple algorithm for finding an inducing n-path for A in O(n log n) time and an algorithm that constructs an inducing n-gon for a special class of line arrangements within the same time bound. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|