Treffer: On the Oß-hull of a planar point set

Title:
On the Oß-hull of a planar point set
Authors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Alegría Galicia, Carlos, Orden, David, Seara Ojea, Carlos, Urrutia Galicia, Jorge
Publisher Information:
2018-03-01
Document Type:
E-Ressource Electronic Resource
Index Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional, Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica, Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Optimització, Geometry, Algebraic, Numerical analysis, Operations research, Restricted-orientation geometry, Convex hull, Area optimization, Perimeter optimization, Fitting, Geometria algèbrica, Anàlisi numèrica, Investigació operativa, Classificació AMS::14 Algebraic geometry::14Q Computational aspects in algebraic geometry, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science, Article
URL:
https://arxiv.org/pdf/1509.02601.pdf
http://hdl.handle.net/2117/180893
https://www.sciencedirect.com/science/article/abs/pii/S0925772117300469?via%3Dihub
Availability:
Open access content. Open access content
Open Access
Note:
15 p.
application/pdf
English
Other Numbers:
HGF oai:upcommons.upc.edu:2117/180893
Alegría-Galicia , C. [et al.]. On the Oß-hull of a planar point set. "Computational geometry: theory and applications", 1 Març 2018, vol. 68, p. 277-291.
0925-7721
10.1016/j.comgeo.2017.06.003
1151825640
Contributing Source:
UNIV POLITECNICA DE CATALUNYA
From OAIster®, provided by the OCLC Cooperative.
Accession Number:
edsoai.on1151825640
Database:
OAIster

Weitere Informationen

© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0
We study the Oß-hull of a planar point set, a generalization of the Orthogonal Convex Hull where the coordinate axes form an angle ß. Given a set P of n points in the plane, we show how to maintain the Oß-hull of P while ß runs from 0 to p in T(n log n) time and O(n) space. With the same complexity, we also find the values of ß that maximize the area and the perimeter of the Oß-hull and, furthermore, we find the value of ß achieving the best fitting of the point set P with a two-joint chain of alternate interior angle ß.
Peer Reviewed
Postprint (author's final draft)