Loading...
Please wait, while we are loading the content...
Similar Documents
Computing Triangulations with Minimum Stabbing Number
| Content Provider | Semantic Scholar |
|---|---|
| Author | Alvarez, Victor Fekete, Sándor P. Schmidt, Arne |
| Copyright Year | 2017 |
| Abstract | For a given point set P or a polygon P , we consider the problem of finding a triangulation T with minimum stabbing number, i.e., a triangulation such that the maximal number of segments hit by any ray going through T is minimized. We prove that this problem is NP-hard; this differs from the problem of triangulating a polygon with minimum edge weight, which is solvable in polynomial time with a simple dynamic program [7]. In an experimental part we test various heuristics. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.victoralvarez.net/papers/Computing%20Triangulations%20with%20Minimum%20Stabbing%20Number%20-%20EuroCG%202017.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
