DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, HK | - |
dc.contributor.author | Sang Won Bae | - |
dc.contributor.author | Marc van Kreveld | - |
dc.contributor.author | Iris Reinbacher | - |
dc.contributor.author | Bettina Speckmann | - |
dc.date.accessioned | 2016-03-31T09:18:46Z | - |
dc.date.available | 2016-03-31T09:18:46Z | - |
dc.date.created | 2012-01-11 | - |
dc.date.issued | 2011-12-06 | - |
dc.identifier.issn | 0166-218X | - |
dc.identifier.other | 2011-OAK-0000024478 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/16992 | - |
dc.description.abstract | We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Theta(n(2)) and Theta(n(3)) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Theta(n(3)) and Theta(n(6)). If we count only star-shaped pseudo-triangles, the bounds are Theta(n(2)) and Theta(n(5)). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n(3)) time. In the general case, the running times are O(n(6)) for the maximization problems and O(n log n) for the minimization problems. | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | Elsevier | - |
dc.relation.isPartOf | DISCRETE APPLIED MATHEMATICS | - |
dc.title | Empty Pseudo-Triangles in Point Sets | - |
dc.type | Article | - |
dc.contributor.college | 컴퓨터공학과 | - |
dc.identifier.doi | 10.1016/j.dam.2011.07.026 | - |
dc.author.google | Ahn H.-K., Bae S.W., Van Kreveld M., Reinbacher I., Speckmann B. | - |
dc.relation.volume | 159 | - |
dc.relation.issue | 18 | - |
dc.relation.startpage | 2205 | - |
dc.relation.lastpage | 2213 | - |
dc.contributor.id | 10152366 | - |
dc.relation.journal | DISCRETE APPLIED MATHEMATICS | - |
dc.relation.index | SCI급, SCOPUS 등재논문 | - |
dc.relation.sci | SCI | - |
dc.collections.name | Journal Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | DISCRETE APPLIED MATHEMATICS, v.159, no.18, pp.2205 - 2213 | - |
dc.identifier.wosid | 000299144500001 | - |
dc.date.tcdate | 2019-01-01 | - |
dc.citation.endPage | 2213 | - |
dc.citation.number | 18 | - |
dc.citation.startPage | 2205 | - |
dc.citation.title | DISCRETE APPLIED MATHEMATICS | - |
dc.citation.volume | 159 | - |
dc.contributor.affiliatedAuthor | Ahn, HK | - |
dc.identifier.scopusid | 2-s2.0-82955247656 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | Article | - |
dc.subject.keywordAuthor | Finite planar point set | - |
dc.subject.keywordAuthor | Pseudo-triangle count | - |
dc.subject.keywordAuthor | Optimal pseudo-triangle computation | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Mathematics | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.